The Computational Geometry Column #2
Joseph O'Rourke
Department of Computer Science
Johns Hopkins University
Baltimore, MD 21218
(301) 338-8468
Two of the open problems posed in the first computational geometry column [1] have been solved. I will describe those solutions and report on new problems presented at three recent conferences [4,5,6].
First, a correction. The linear-time polygon triangulation result I mentioned in [1] has slipped a bit to O(nloglogn). Robert Tarjan and Christopher VanWyk discovered an oversight in the analysis presented in their STOC abstract and have corrected it in the full paper [7]. The result is a simpler algorithm, but with a slightly higher worst-case complexity. O(nloglogn) still represents a significant breakthrough, but leaves open the question of whether a triangulation of a simple polygon can be found in linear time.
Open problem number (7) from [1] was in fact solved at the Yorktown conference by William Thurston. Recall that Raimund Seidel posed the problem of determining whether a finite set of non-intersecting lines in Euclidean three-dimensional space always may be ``parallelized'': rearranged by continuous motion so that they all become parallel to one another, without two lines ever intersecting during the rearrangement. The answer is yes! Thurston's proof is concise and elegant.
Establish an XYZ Cartesian coordinate system so that no lines are parallel to the YZ-plane. Since there are a finite number of lines, this can always be done. Expand the space in the X-direction by a factor of t ý 0: map each point (x,y,z) to (tx,y,z). It is clear that this expansion does not cause any lines to intersect. Now let t b . Since no line is parallel to the YZ-plane, this expansion rotates every line until they are all parallel to the X-axis. The conclusion is that, in some sense, all arrangements of lines in three-dimensional space are equivalent.
Open problem (8) from [1] asked if every Delaunay triangulation contains a Hamiltonian cycle. It has been solved negatively by Michael Dillencourt: he found a Delaunay triangulation of 9 points that contains no Hamiltonian cycle [2]. His example becomes Hamiltonian, however, if the edges of the furthest-point Voronoi diagram dual are added, so Seidel's question of whether every spherical (inscribable) polytope skeleton is Hamiltonian remains open. In addition, my question of whether every Delaunay triangulation contains a perfect matching (one of size Ðn/2) also remains open, as his example has a matching of size 4. Dillencourt also obtained the following nice positive result: every Delaunay triangulation is 1-tough, that is, removal of k vertices disconnects the graph into at most k connected components. If a graph is Hamiltonian, it is 1-tough, but the converse does not necessarily hold.
The following are a selection of new problems posed in problem sessions at recent conferences.
(1) Raimund Seidel posed a problem closely related to the Hamiltonian cycle question [5]. Let
T and
T
` be two triangulations of a convex
n-gon that do not share a diagonal. Is it always possible to find
n points in
R
3 such that their convex hull
H
(a) projects to a convex n-gon on the XY-plane and
(b) the collection of top faces of H (those whose outward normals have positive Z-component) is combinatorially isomorphic to T and the collection of bottom faces is isomorphic to T `?
The answer is known to be yes if T is a star: all diagonals are incident to a common vertex. Note that if no face of H is parallel to the Z-axis, H necessarily has a Hamiltonian cycle: the cycle that projects to the n-gon in the XY-plane.
(2) I posed two shortest path problems; the first is solved, but the second is open. Both seek specializations of the obstacles so that the usual quadratic worst-case time complexity can be beaten.
The first asks whether every simple (non-intersecting) polygonal path in the plane is a shortest path around a finite collection of open line segments whose closures are disjoint [6]. In other words, if the obstacles are line segments, can any restriction be placed on the shape of the shortest paths? Lee and Preparata established in 1984 that if the obstacles are vertical line segments, the shortest paths must be monotone with respect to the horizontal and this characterization enabled them to construct an O(nlogn) algorithm. Disappointingly, Jeff Kahn and Peter Ungar (independently) sketched a construction that shows that no such characterization is possible when the segments have arbitrary orientation: any polygonal path can be forced to be the shortest path between its endpoints by surrounding it with a finite number of line segment obstacles. The details of the construction remain to be worked out; perhaps an exponential number of segments are needed (exponential in the number of path turns).
The second problem is to find a shortest path between two points in the plane that avoids a collection of n disjoint congruent open disks in subquadratic (o(n2)) time [5]. Note that because the disks are disjoint and open, the path can always slip between any two of them. Again it would be nice to characterize the shape of such shortest paths. Surprisingly, the shortest path may spiral with arbitrary winding if the disks are not congruent. This seems impossible with congruent disks, but even with congruent disks, the path may be non-monotone.
(3) Michael McKenna posed what he called the ``biggest stick'' problem [4]: find the longest line segment completely contained within a simple polygon of
n vertices; the polygon is considered a closed set, so the segment may touch the boundary at one or more points. McKenna established that the biggest stick must pass through two vertices of the polygon. This leads to an easy O(
n
2) algorithm: For each vertex
x, compute its visibility polygon
V(
x) (the region visible from that vertex) in O(
n) time and sweep a line angularly around
x, stopping at each vertex
y of
V(
x) to compute the longest segment passing through
x and
y. McKenna's problem asked for a subquadratic algorithm.
Micha Sharir has found an O(n2e) algorithm, where e > 0 is quite small; its exact value is not yet worked out. He first reduced the problem to that of finding the maximum of two bivariate functions. Let F1(x,y) and F2(x,y) be two piecewise smooth functions such that the projections of the smooth portions onto the XY-plane form a straight-edge convex subdivision of the plane. Sharir showed that maxx,y[F1(x,y)+F2(x,y)] can be found in O(n2e) time if the smooth portions are such that it is known that the maximum is achieved either at a vertex of one of the convex subdivisions or an intersection point between two of the subdivision edges. This condition is satisfied if, for example, the functions are piecewise linear. His technique employs Collins' cylindrical algebraic decomposition technique.
The connection between the biggest stick problem and this function maximizing problem is as follows. Divide the original polygon P at a diagonal d into two nearly equal-sized pieces P1 and P2. Recursively compute the biggest stick in each half. The merge step requires the biggest stick that crosses d. Let s be such a stick. The length of s in P1 (i.e., |s ) P1|) can be considered a function F1 of two parameters, for example, of the location of s ) d and the angle between s and d. Actually it is more convenient to use a different parametrization based on the dual, but let's ignore that detail. Let F2 be the function whose value is the length of s in P2. When the arguments to F1 and F2 are identical, the corresponding half-sticks line up. Thus the length of the biggest merge stick is given by the maximum of F1+F2.
Despite Sharir's breakthrough, McKenna's problem remains open in the sense that it seems unlikely that Sharir's upper bound is also the lower bound.
(4) Chee Yap posed a series of problems that attracted much attention [4]. I will just mention one and refer readers to his paper for the others [8]. Define a ring of width w to be simply two points in the plane separated by distance w. (Imagine they are the intersection of the plane with a circular ring perpendicular to the plane.) Suppose the ring can ``pass over'' a polygon P in the sense that the two points can be moved so that they are never interior to P and such that every interior point of P is crossed by the segment connecting the ring points a net of one time. The precise definition of this passing over concept is a bit tricky, since the ring may cross a point several times in different directions; see [8] for details. Yap's conjecture was: if a ring of width w can pass over P, then so can a ring of any wider width w` ý w. This sounds obvious with no thought, false after some thought and true after considerable thought. It was proven independently by David Eppstein and J anos Pach; several others had proven it in special cases. John Kutcher and I have implemented a simple O(n2) algorithm that, given the paths of the two ring points, will move a ring of any wider width down the same paths.
(5) Robert Connelly posed the ``circuit board'' problem [6]: given 2n points in the closed unit square a1 , . . . , an and b1 , . . . , bn, find non-crossing paths connecting ai to bi, 1 d i d n, such that the sum of the path lengths is minimized. Which configurations of points achieve the largest sum of path lengths for each n? It seems clear that in these worst-case configurations, all the terminal points are on the boundary of the square, but otherwise little seems to be known.
(6) Micha Sharir asked [4] for an algorithm to construct the convex hull of n (perhaps overlapping) spheres. He has found an example where the combinatorial complexity of the hull is W(n2), in marked contrast to the hull of, say, n points in three dimensions, which has O(n) vertices, edges and faces.
(7) J anos Pach communicated a problem of unknown origin [5]. Let A and B be two sets of n points each in R3 such that the minimum distance between any point a A and any point b B is 1. What is the maximum number of pairs (a,b) that can realize the distance 1? A similar problem where the point set is not partitioned into two parts has been studied extensively (e.g., [3]), but the problem as stated seems rather different. Alok Aggarwal added an algorithmic question: under the same assumptions, find an algorithm that computes a pair (a,b) of points that is separated by distance 1. He has an O(n3/2(logn)1/2) algorithm and asks for an o(n3/2) algorithm.
References
[1] O'Rourke, J. Computational Geometry Column #1. SIGACT News 18, 1, (Summer 1986), 17-19. Also in Computer Graphics 20, 5, (Oct. 1986), 232.
[2] Dillencourt, M. A non-Hamiltonian, nondegenerate Delaunay triangulation. IPL, to appear, 1987.
[3] Erdos, P. On sets of distances of n points. Amer. Math. Monthly 53 (1946) 248-250.
[4] First Computational Geometry Day, New York University, 19 September 1986.
[5] Second Computational Geometry Day, New York University, 14 November 1986.
[6] AMS Conference on Discrete and Computational Geometry, University of California at Santa Cruz, 20-26 July 1986.
[7] Tarjan, R.E. and Van Wyk, C.J. An O(nloglogn) algorithm for triangulating simple polygons. AT&T Bell Laboratories manuscript, 1986.
[8] Yap, C.K. How to move a chair through a door. To appear in IEEE Journal of Automation and Robotics, 1987.
(Written 19 Nov. 1986)