| ||
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
where R ‰ = ˆ n n and C is discrete, i.e., for each n , the set { P ( x ) x ˆˆ n } is finite. For example, the 2D convex hull problem maps 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
The input space X = nd has the standard Euclidean topology. The output space Y is the product C — m of a finite space C with discrete topology and the Euclidean space 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 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 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 , ( x ) ˆˆ Y represents the outcome of a geometric algorithm designed to solve P . An algorithm computes P exactly for x ˆˆ X , if ( x ) = P ( x ).
Definition 9.3. (Robust geometric algorithm.) A geometric algorithm is called robust , if for all x ˆˆ X , there is x ˆˆ X such that ( x ) = P ( x ); i.e., the output of the algorithm gives at least a correct result for a correct input x . The algorithm is called stable , if for all x ˆˆ X , there is x ˆˆ X near to x such that ( 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 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 ( x ) = P ( x ) and
Here, refers to the accuracy of the given number representation and ~ means the maximum norm. For a stable algorithm, f ( n, ) should be as small as a function in n and . A very stable algorithm should be independent from n and should guarantee f ( n, ) ˆˆ O ( ).
We will give a simple motivation for this concept. Let us assume that an algorithm 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 , see Section 9.3.1 for details, is given. This means that a number can be represented in the computer by approximately k = ˆ log bits. Rounding all numbers approximately to k/d bits allows exact computations . This is a perturbation of O ( ˆ d ). Altogether, in the given situation, a perturbation bound of f ( n, ) ˆˆ O ( ˆ d ) should be achievable. This is denoted also as a perturbation bound benchmark ; see [Fortune 89].