9.2. Formal Definition of Robustness and Stability

9.2. Formal Definition of Robustness and Stability

We follow the lines of [Fortune 96, Fortune 89] and will give a formal definition of robustness. In a mathematical sense, a geometric problem is a mapping from an input set of geometric objects to an output set of geometric objects.

Fortune [Fortune 96, Fortune 89] suggests to define a geometric problem by a function

image from book

where R = ˆ n image from book n and C is discrete, i.e., for each n , the set { P ( x ) x ˆˆ image from book n } is finite. For example, the 2D convex hull problem maps image from book n for even n onto cyclically ordered subsets {1 , 2 , , n /2} indicating the indices of the counterclockwise sequence of the points on the convex hull. By representing the DCEL in an appropriate manner, the arrangement problem in Section 9.1.1 can be easily transformed into this framework.

To be more precise and to be consistent with the formal definition of degeneracy in Section 9.5.1, we use the following concept.

Definition 9.1. (Geometric problem.)   A geometric problem is a function

image from book

The input space X = image from book nd has the standard Euclidean topology. The output space Y is the product C image from book m of a finite space C with discrete topology and the Euclidean space image from book m .

Here m , n , and d are integers, and C is a discrete space that represents the combinatorial part of the output; for instance a planar graph or an ordered list of vertices. The parameter d represents the dimension of the input space, and n represents the number of input points. This formalism is equivalent to the definitions in Section 9.5.1.

For example, the 2D convex hull problem maps image from book 2 n onto cyclically ordered subsets {1 , 2 , , n } indicating the indices of the counterclockwise sequence of the points on the convex hull. The set of all ordered subsets of {1 , 2 , , n } represents the discrete set C .

The arrangement problem in Section 9.1.1 can be easily transformed into this framework. C represents the planar graph of the arrangement; and the intersections are represented within image from book m .

Definition 9.2. (Selective geometric problem.)   A geometric problem is called selective if the output P ( x ) ˆˆ C selects only elements out of the input set x , for example, the convex hull problem is selective. A constructive geometric problem represents new objects in the output P ( x ).

For example, the DCEL of the line segment arrangement of Section 9.1.1 consists of vertices stemming from the intersections of two line segments. In this sense, the corresponding algorithm is constructive.

For x ˆˆ X , image from book ( x ) ˆˆ Y represents the outcome of a geometric algorithm image from book designed to solve P . An algorithm image from book computes P exactly for x ˆˆ X , if image from book ( x ) = P ( x ).

Definition 9.3. (Robust geometric algorithm.)   A geometric algorithm image from book is called robust , if for all x ˆˆ X , there is x ˆˆ X such that image from book ( x ) = P ( x ); i.e., the output of the algorithm gives at least a correct result for a correct input x . The algorithm image from book is called stable , if for all x ˆˆ X , there is x ˆˆ X near to x such that image from book ( x ) = P ( x ).

Robustness guarantees that the output of the algorithm is correct for some perturbation of the input. The algorithm is stable if the perturbation is small. Note that we cannot compare two outputs A ( x ) and A ( x ) in the same way. In many applications, the output A ( x ) of an algorithm is not continuous in x . For example, the resulting graph of the arrangement problem may change fundamentally, although the input is only slightly perturbed.

A stable algorithm is accompanied with a measure of the perturbation bound.

Definition 9.4. (Relative error.)   Algorithm image from book for problem P has relative error f ( n, ), if for all x ˆˆ X with x ˆˆ O ( n ), there is an x ˆˆ X near to x so that image from book ( x ) = P ( x ) and

image from book

Here, image from book refers to the accuracy of the given number representation and ~ means the maximum norm. For a stable algorithm, f ( n, image from book ) should be as small as a function in n and image from book . A very stable algorithm should be independent from n and should guarantee f ( n, image from book ) ˆˆ O ( image from book ).

We will give a simple motivation for this concept. Let us assume that an algorithm image from book internally handles polynomials with degree at most k , i.e., every computation can be performed by evaluation of multi-variable polynomials of degree d . For example, p ( x, y ) = x 3 y 5 + x 4 y 2 + 7 is a multi-variate polynomial of degree 8. Let us further assume that a machine error image from book , see Section 9.3.1 for details, is given. This means that a number can be represented in the computer by approximately k = ˆ log image from book bits. Rounding all numbers approximately to k/d bits allows exact computations . This is a perturbation of O ( image from book ˆ d ). Altogether, in the given situation, a perturbation bound of f ( n, image from book ) ˆˆ O ( image from book ˆ d ) should be achievable. This is denoted also as a perturbation bound benchmark ; see [Fortune 89].



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net