Distinct distances determined by subsets of a point set in space

Reviewer: Joseph J. O'Rourke

In a 1989 survey talk, I predicted that two new journals devoted to computational geometry would appear within a decade. My prediction was realized in under two years, with the publication of the International Journal of Computational Geometry and Applications, edited by D. T. Lee, and Computational Geometry: Theory and Applications, the journal under review. This journal mentions “theory” in its title, while Lees journal does not, and one might therefore expect a slight separation between the two along the theory-applications continuum. The first issue of this journal contains four papers ranging in scope from pure theory to practical theory. Avis, Erdo&huml;s, and Pach The first paper, by Avis, Erdo&huml;s, and Pach, contributes to our understanding of the difficult combinatorics of distinct distances determined by a set of points, an area initiated and extensively explored by Erdo&huml;s. Four points on a line usually determine 4 2 =6 distinct distances, but four equally spaced points only determine three distinct distances. One would expect most four-element subsets of a large set to determine six distances, even if the set is highly regular. A typical result from this paper confirms and quantifies this intuition: as n tends to infinity, almost all k -element subsets of n points in the plane determine k 2 distinct distances, if k is small relative to n : k=o n 17 . de Berg The second paper, by de Berg, studies orthogonal (or rectilinear) link distance in an orthogonal polygon: the minimum number of horizontal and vertical segments in a path connecting a pair of points, in a polygon itself composed entirely of horizontal and vertical edges. His results hinge on an extension of Chazelles polygon-cutting theorem to the orthogonal world: an orthogonal polygon with weighted vertices can be cut in two with a horizontal or vertical chord so that the weight of each piece is at most 34 of the total. This theorem leads (among other results) to an algorithm for computing the orthogonal link diameter in O n log n time for an orthogonal polygon of n vertices. Overmars and Sharir In the third paper, Overmars and Sharir show how to merge visibility maps efficiently. Visibility maps are subdivisions of a viewing window into regions within which only one object is visible, computed by object-space hidden surface removal algorithms. Merging of maps is useful, for example, in animation, where the map of the environment is fixed and a moving object map needs to be interleaved with the environment map. Perhaps more important, map merging is a step toward a truly output-size sensitive hidden surface algorithm, one dependent more on k , the size of the output visibility map, than on n , the size of the input. For example, Overmars and Sharir obtain an algorithm for hidden surface removal for a scene of n disjoint unit spheres that requires O n+k log 2 n time, considerably better than the nai¨ve O n 2 algorithm. Seidel The final paper in this issue, by Seidel, offers a simple and fast randomized polygon triangulation algorithm. Chazelles breakthrough discovery of an O n deterministic algorithm settled the theoretical issue, but practical algorithms that approach the theoretical speed achievements have remained elusive. Seidels algorithm is remarkably simple: insert the edges of the polygon into a simple “trapezoidation” data structure in random order, and every once in a while ( log * n times), update some information in the structure. The result is an O n log * n expected-time algorithm that avoids divide-and-conquer, complex data structures, and other implementation hurdles.