9.5. Degeneracy

9.5. Degeneracy

In the preceding section, we already noticed some of the influences of degeneracy. For example, if three points are almost colinear or if four points appear to be almost coplanar, the computation of the coordinates of circumcenters and circumspheres may become unstable. These cases are based on the fact that roundoff errors prevent us from exact calculations. In the following, we will assume that we are able to calculate geometry-based expressions exactly. In this case, we are able to detect degeneracy and only the algorithmic problem of dealing with degenerate cases remains. We will focus on the algorithm-dependent degeneracy.

Many geometric algorithms are designed and analyzed under the assumption that degenerate cases do not occur. The main reason is that degeneracy may evoke case distinctions that let the solution appear inelegant, and sometimes completely destroys the complexity analysis. Additionally, degenerate cases are not useful for explaining the intrinsic idea of a geometric algorithm.

9.5.1. Formal Definition of Degeneracy

We repeat the notations from [Emiris and Canny 92]. Formally, we consider a geometric problem P as a mapping between topological spaces X and Y . 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 non-negative integers, and C is a discrete space that represents the combinatorial part of the output, such as 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. Note that this formalism is equivalent to the definitions in Section 9.2.

Definition 9.31. (Degenerate problem.) A problem instance x ˆˆ image from book nd of a geometric problem P is said to be degenerate iff P has a discontinuity at x .

For example, let d = 2 and consider n points in the plane. Let P ( x ) denote the Voronoi diagram of the input points (see Chapter 6); that is, a straight line planar graph, represented in C , and the coordinates of its vertices represented in image from book m . There is a discontinuity at x if there are four points on a circle that represent a common vertex.

Under the EGC paradigm (see Section 9.3.4), any geometric algorithm that solves a geometric problem should be driven by geometric predicates only. That is, every branch of an algorithm depends on the sign of a predicate. Therefore, we can consider a geometric algorithm A as a simple decision tree, where the decision nodes test the sign of a (usually low degree) polynomial of the input variables .

Definition 9.32. (Degenerate algorithm.) An instance x of a geometric algorithm A , where A solves problem P , is called degenerate if the computation of A on input x contains a predicate test with output zero.

Typical cases for degeneracy are three points on a line, four points on a circle, or two points with the same x -coordinate. Degenerate cases may lead to difficult case analysis in a corresponding algorithm, so they should be avoided. In the following, the input is said to be in general position if degeneracy does not occur. Degeneracy is closely related to corresponding predicates; for example, the case of three points on a line corresponds to O2D, and the case of four points on a circle corresponds to In2D.

The following methods increase the computational complexity of a corresponding algorithm. We will make use of the Real RAM model described in the beginning of Section 9.3. Only the four basic operations {+ , ˆ , , / }are allowed between real numbers . We consider the maximal computation cost of the longest computation path in the decision tree of a geometric algorithm. Two different complexity measures will be discussed. In the algebraic model , we count unit cost for every vertex in the computation path along the decision tree. In the bit model , we also keep track of the bit size of the corresponding operands, which is more realistic. For integers of size O ( b ), addition and subtraction need O ( b ), whereas multiplication and division require M ( b ) bit operations, where M ( b ) := O ( b log b log log b ) is an upper bound on the bit complexity of any operation in the RAM; see [Aho et al. 74]. The total bit complexity is given by the maximum of the sum of the bit operations of any computation path.

9.5.2. Symbolic Perturbation

In this section, we will discuss the generic technique of a symbolic perturbation. The input is perturbed symbolically so that a general position is enforced. Thus, for a probably degenerate input x , we obtain a non-degenerate input x ( image from book ) and compute P ( x ( image from book )) with algorithm A . In a post-processing step, we obtain the answer P ( x ) from P ( x ( image from book )).

There are several perturbation methods discussed in the literature. The idea of a perturbation of the input values goes back to symmetry breaking rules in linear programming; see [Dantzig 63]. The right-hand side of the i th constraint

image from book

is perturbed by an infinitesimal quantity that depends on the index i of the constraint and becomes

image from book

where x 1 , x 2 , , x n are the original variables, x n + i are the slack variables, and the values a ij and b i are constants. The perturbation method avoids infinite cycles in a simplex algorithm.

Let us assume that x ij are the input coordinates of our problem. For example, we have n points x i = ( x i 1 , x i 2 , , x id ) for i = 1 , , n in the d -dimensional Euclidean space.

Definition 9.33. (Valid perturbation.) Per [Emiris and Canny 92], a perturbation x ( image from book ) for an input instance x is called valid iff

  • x ( image from book ) is in general position,

  • x ( image from book ) is arbitrarily close to x such that

  • whenever x is non-degenerate, x and x ( image from book ) evoke the same computation path in the corresponding geometric algorithm.

A perturbation is called symbolic if the perturbation values are never evaluated exactly.

Note that general position corresponds to a (set of) geometric predicate(s). Symbolic perturbation schemes are never evaluated exactly, but we have to rewrite the corresponding predicates. Depending on the perturbation scheme, this is more or less efficient. The symbolic variable image from book will never be evaluated exactly. The focus is on the proof of the existence of a small perturbation image from book that fulfills the validity conditions.

Edelsbrunner and M



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