On Removing Extrinsic Degeneracies in
Computational Geometry

Project for CS507 - Computational Geometry  (Prof. Godfried T. Toussaint)
Presented by  Qing hu Liao
December 2, 2003

Introduction

Algorithms in computational geometry are usually designed for the real RAM (random access machine) assuming that the input is in general position.  The general position assumption implies that the input to an algorithm for solving a specific problem is free of certain degeneracies.  There are two kinds of degeneracies:

• Intrinsic (problem-induced). for example, in computing the convex hull, three collinear points is problem-induced degeneracy.
• Extrinsic (algorithm-induced). for certain vertical line-sweep algorithms, two points with the same x-coordinates constitute an algorithm-induced degeneracy.

Existing methods for removing degeneracies in computational geometry can be classified as either:

• Approximation.
• Perturbation.
The above methods give the implementer two rather unsatisfactory choices: find an approximation of the original problem given, or find an exact solution to an approximation of the original problem. Sometime it may be possible to convert the approximate solution obtained from perturbation methods to the exact solution by using some kind of post-processing step, but this step may be difficult and complicated.

Gomez, Ramaswami and Toussaint[1] give an alternative approach for removing extrinsic degeneracies:
• Some Extrinsic degeneracies can in fact be removed by a global rigid transformation. Once the solution is obtained on the transformed non-degenerate input, it can be transformed back trivially to yield the solution to the original problem.
We  will consider several non-degeneracy assumptions that are typically made in the literature:
And for each case we will consider the decision problem, computation problem, and optimization problem.

Definitions

• Regular projection:
• A projection of point set S (n points) on a line L is said to be regular if each point in S projects to a distinct point on L. In other words the project contains n distinct points.
• Let S be a set of n distinct points in Euclidean space and Let H be a plane, a projection of S on H is said to be regular if each point in S projects to a distinct point on H.
• Maximum projective tolerance:
• The projection that allows the greatest angular deviation of the viewpoint without violating the regularity of the projection, i.e,. without creating degeneracies. We call this regular projection with maximum projective tolerance.

Degeneracy 1: no two points in the plane have the same x-coordinate

Figure 1: A non-regular projection of points(2D) on the x-axis.

## The Decision Problem

A very simple algorithm suffices since we simply need to check for duplicates in the x-coordinate values of the point set S. this can be done in O(n log n) time by sorting these values. The projection is regular if and only if there are no duplicates. The lower bound can be established  by a reduction from the element-uniqueness problem.

Theorem 1.1: Given a set of S of n distinct points in the plane and a line L, whether S admits a regular onto L can be determined in O(n log n) time.

## The Computation problem

Given a set S of n distinct points in the plane, find a rotation of S that removes the degeneracies, or equivalently, a line L such that S yields a regular projection on L. A regular projection always existed because the only forbidden directions of projections are those determined by the lines through pairs of points of S, see Figure 2.

Figure 2: construct the forbidden directions by connecting each pair of points in S

Let the circle C2, representing the set of forbidden directions, be the unit circle in the plane, centered at the origin. For every pair of points in S, translate the line through them so that it intersects the origin. Intersect each such line with C2 to yield a pair of forbidden points on C2.  Altogether there are O(n2) such forbidden points. see Figure 3.

Figure 3:  construct the forbidden points on unit circle.

We may determine a direction for a regular projection by finding a point in the interior of any arc of C2 that is bounded by two distinct adjacent forbidden points. Such a point on C2 may be found easily in O(n2 log n) time by using the brute-force approach of sorting the forbidden points.

A quicker approach is generate a random direction points on C2, check if it is conflict with the existing forbidden points, if not, we get the desired rotation scheme. if it does conflict with the existing forbidden points, we regenerate another random points, and continue to check it.  The total excepted run time should be O(n2).

Actually we can get this by O(n log n) time. See Figure 3, let 'a'to be the points with largest slope which lies on y-axis, if we can find the second largest slope (say 'b'), then we can choose any point (say 'c') in the arc between 'a' and 'b'. rotate the y-axis to align with 'c', we can get the regular projection.  how could we find the second largest slope? there is a trick, in fact we don't really compute and find the second largest slope which will take O(n2) time, we just find its upper bound. this is can be done as follows:
1. Find the largest and smallest y-coordinate of the points in S,  we get maxS(delta(y)) = ymax - ymin.  ---  O(n) time.
2. Sort the x-coordinates of the points in S, and discard the duplicates, find the smallest the gap minS'(delta(x)). ---  O(n log n) time.
3. Compute the upper bound for the Second largest slope:
maxS(delta(y)) / minS'(delta(x))

Where S' is the distinct projection points of S on x-axis. We can easily see this value is not less than the second largest slope. see Figure 4.

Figure 4: Computing abound on the second largest distinct slope.

Proof:
1. we know the second largest slope = maxS(delta(y)/delta(x)),  when delta(x) != 0.
2. and it is easily to see: maxS(delta(y)/delta(x)) <= maxS(delta(y)) / minS'(delta(x)).

Theorem 1.2: Given a set of S of n distinct points in the plane, finding a regular projection takes O(n log n) time.

## The Optimization Problem

We consider now the question of not merely removing the degeneracies (finding a regular projection), but removing them in the best way possible, say with maximum projective tolerance.

See Figure 3,  we know this question is determined by the mid-point of the largest gap among consecutive forbidden points on C2,  the circle of directions.  The  largest gap can be found by sorting the O(n2) forbidden points.

Theorem 1.3: Given a set of S of n distinct points in the plane, a regular projection with the maximum projective tolerance can be computed in O(n2logn) time and O(n2) space.

Degeneracy 2: no two points in space lie on a vertical line

## The Decision Problem

Figure 5: A non-regular projection of points(3D) on the xy-plane.

Let S be a set of n distinct points in Euclidean space and Let H be the xy-plane,  no two points in space lie on a vertical line if each point in S projects to distinct point on H.  See Figure 5: point 2, 3 have same project point on xy-plane. so it isn't a regular projection.

Let Sxy denote the set of points obtained by projecting S onto the H (xy-plane).  First, sort the points in Sxy lexicographically by x and y coordinates.  Scan through the sorted list to determine whether two (or more) points in Sxy have the same x and y coordinates, we can tell whether there are vertical line degeneracies. which takes O(n log n) time.

Theorem 2.1: Given a set of S of n distinct points in space and a plane H, determining whether S admits a regular projection onto H takes O(n log n).

## The Computation problem

As in the 2D case, the only forbidden directions of projections are given by line in space going through pairs of points in S, because S does not admit a regular projection onto planes perpendicular to these lines. By translating every such line to origin and intersecting it with the sphere of directions, we obtain O(n2) (not necessarily distinct) forbidden points on C3.

Figure 6: forbidden points on unit sphere and its latitude circle.

if S doesn't project regularly onto the xy-plane, then there is at least one forbidden point at the "north-pole" of the sphere, say it is M1,  Let Mdenote the second largest slope point, we know any sphere point in the latitude circle of M2 except M1 can yield a regular projection. See Figure 6.

Figure 7: Fast algorithm for upper bound of the second largest slope.

As in 2D case, we will compute the upper bound of the second largest slope, instead of  the second largest slope.  the algorithm follows:
1. Let Sxy, Sx and Sy denote the sets of points obtained by projecting S onto the xy-plane, x-axis and y-axis, respectively.
2. Sort each of Sxy, Sx and Sy lexicographically.  --- O(n log n) time.
3. Scan through each sorted list to remove multiple occurrences of a point ( keeping one copy). Call these new sorted lists Sxy*, Sx* and Sy*, respectively.
4. Compute the width of S in the z-direction.  maxS{delta(z)}. Also compute d = min{minSx*{delta(x)}, minSy*{delta(y)}}.
5. The upper bound of the second largest slope M2 is maxS{delta(z)} / d.
Proof:
1. The second largest slope = maxS(delta(z)/sqrt(delta(x)*delta(x) + delta(y)*delta(y))),  when delta(x)*delta(x) + delta(y)*delta(y) != 0.
2. and it is easily to see: maxS(delta(z)/sqrt(delta(x)*delta(x) + delta(y)*delta(y))) <= maxS{delta(z)} / d.

Theorem 2.2: Given a set of S of n distinct points in space, finding a regular projection of S takes O(n log n) time.

## The Optimization Problem

As in the 2D case, it is desirable to remove vertical-line degeneracies in an optimal way, i.e., a direction of projection from which we can deviate the most without introducing degeneracies.

Figure 8: The largest empty circle on the surface of the direction sphere.
It is easily to see that such a direction should be determined by the center of the largest empty circle among the m = O(n2) forbidden points on C3,  See Figure 8.
1. Find and discard all duplicate points on C3 by performing a lexicographic sort of the forbidden points.  ---  O(m log m)
2. Computing the convex hull of the points.  ---  O(m log m)
3. Computing The Voronoi diagram on the sphere from the convex hull in linearly time.  ---  O(m).  The lower convex hull when projected to the plane is the Delaunay triangulation which is the dual of the Voronoi diagram and can be computed trivially from it.  See Brown[3] for detail.
4. get the largest empty circle. O(m).
5. the optimal direction is determined by the center of the empty largest circle.
Theorem 2.3: Given a set of S of n distinct points in space, a regular projection plane with the maximum projective tolerance can be computed in O(n2 log n) time and O(n2) space.

# Degeneracy 3: no two points in space have the same x-coordinates

## The Decision Problem

By sorting the points of S by their x-coordinate value, we can determine if any two points of S have the same x-coordinate, i.e., if the projection onto the x-axis is regular or not. Once again, we reduce element-uniqueness to this problem to show an Omega(n log n) lower bound.

Theorem 3.1: Given a set of S of n distinct points in space, whether S admits a regular projection onto the x-axis can be determined in O(n log n) time.

## The Computation problem

The problem is find a line L that S yields a regular projection onto L. This can be done as follows:
1. First find a plane of regular projection for S.  Let H be such a plane and let SH be the planar set of points obtained by projecting S onto H. ---  O(n log n) time,  Theorem 2.2.
2. In the plane H, find a line of regular projection for SH.  Let L be such a line. Since there are no duplicates in SH, L is also a line of regular projection for S. --- O(n log n) time, Theorem 1.2.
3. Finally, we can translate and rotate the line L so that it coincides with the x-axis. See Figure 9.

Figure 9: two steps to find a regular projection.

Theorem 3.2: Given a set of S of n distinct points in space,  a rotation of S such that no two points have the same x-coordinate can be computed in O(n log n) time.

This result also can be generalized so that no two points have the same coordinate for two or all three coordinates axes can be computed in O(n log n) time. See Gomez[1] for detail.

## The Optimization Problem

See Figure 10, we see for any line, say L', which lies on the  plane H perpendicular to the line ab,  points a and b will have the same projection points on L'.

Figure 10: Any projection line lie on the  plane H perpendicular to ab will introduce degeneracy.

Therefore a pair of points in S yields a great circle on the sphere C3 as the set of forbidden directions for the desired x-axis. Thus the entire set S yields an arrangement of O(n2) great circles on C3, See Figure 11.

Figure 11: The largest circle contained in a face of the arrangement.

To find a projection of maximum projective tolerance, we need to find a point on the sphere C3 which is the center of the largest spherical disc contained in a face of the arrangement of great circles.

There are O(n2) great circles with a total of O(n4) intersections in the arrangement. Compute the entire arrangement and the largest spherical disc contained in each face, which takes time linear in the size of the face. It follows a line L in space such that S yields the regular projection onto L with the maximum projective tolerance can be found in O(n4) time and space.

However, this problem could be solved by a different way:
1. As in the Degeneracy 2 case, we compute the forbidden points on the sphere C3 for each pairs points in S. Let Sf denote the forbidden points set.
2. We can prove that finding the largest circle contained in the face of the arrangement (See Figure 11) is equivalent to computing the smallest enclosing cylinder containing Sf.  For the proof, see Gomez[1],
3. Computing the smallest enclosing cylinder containing Sf. ---  O(n3+e), for any e > 0.  Pankakj[2].
4. The axes of the smallest enclosing cylinder is the direction with maximum projective tolerance.

Theorem 3.3: Given a set of S of n distinct points in space,  a line L in space such that S yields a regular projective onto L with the maximum projective tolerance can be found in O(n3+e) time and space, for any e > 0.

Applet

## Implemented Features:

 Decision Computation Optimization Degeneracy 1 yes yes yes Degeneracy 1 yes yes yes Degeneracy 1 yes yes no

## Usages:

1. Click the check-box on the above panel to choose the type of degeneracy you want to play with.
2. In the text-field, fill the number of points you want to generate by random methods,  The  number should be in the range of [4,40].
3. Click the [Random Points] to generate point set, the points generated by random methods alway have degeneracy for the purpose of demonstration.
4. You can use the [Add Point], [Remove Point] to manipulate the point set.
5. You can hold down any mouse button, and drag the mouse in the display region to rotate the view. The lfet region display the point set,  and the right region display the the forbidden direction points on unit circle or on unit sphere.
6. Check the check-box on the bottom panel, to see the projected points.
7. Click [Decision]button to tell whether the given point set is regular.
8. Click [Compute]button to compute the regular projection direction as fast as possible if the the given point set is not regular. after that, the [execute] button is enabled,  you can click it to rotate the point set to get regular projection.
9. Click [Optimize]button to compute the optimal regular projection direction. after that, the [execute] button is enabled,  you can click it to rotate the point set to get optimal regular projection.

Keywords

• General Position: The general position assumption implies that the input to an algorithm for solving a specific problem is free of certain degeneracies.
• Lexicographical Sort:  Compare two points first by its x-coordinate, if they is equal, then compare their y-coordinate, an so on z-coordinate. sort by this way, we mean we do lexicographical sort.
• Great circle: The plane of great circle passes the center of the sphere.

1. Francisco Gomez, Suneeta Ramaswami and Godfried T. Toussaint, "On removing non-degeneracy assumptions in computational geometry," Proceedings of the Italian Conference on Algorithms, March 12-14, 1997, Rome, Italy, pp. 52-63.
2. Pankaj K. Agarwal, Boris Aronov, Micha Sharir, "Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions", May 14, 1997.
3. K. Q. Brown. "Geometric transforms for fast geometric algorithms". Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, Pittsbugh, PA, 1980. Report CMU-CS-80-101.
4. J. O'Rourke (1998). Computational Geometry in C (2nd ed.)

Thanks

• Prof. Godfried T. Toussaint is one of the best professors I have met in my life, he taught us a lot very insightful and interesting things. I benefit from him a lot.
• This web page style is "borrowed" from the "3-Coins Algorithm Tutorial (Greg Aloupis and Bohdan Kaluzny)". Thanks to Greg Aloupis and Bohdan Kaluzny.

Author: Qinghu Liao
Email: qhliaok@hotmail.com
2003-12-2