The Computational Geometry Column Joseph O'Rourke Department of Computer Science Johns Hopkins University Baltimore, MD 21218 (301) 338-8458 orourke@harvard.edu Last year a new conference, the Symposium on Computational Geometry, was established under the joint sponsorship of SIGGRAPH and SIGACT. At the first symposium, held in June 1985 in Baltimore, there was some sentiment for starting a SIG. At the program committee meeting for the second symposium, however, it was decided to start a Computational Geometry Column in the two sponsoring organizations' newsletters instead. This would satisfy the primary need for a communication forum without the substantial overhead of a SIG structure. This is the first installment of the column. The second symposium was held at IBM Yorktown Heights, June 24, 1986. It attracted 198 participants, 12 more than in 1985; 54 of the attendees were students. Statistics provided by the conference chair, Alok Aggarwal of IBM, show that the conference was dominated by North America, although 10 other countries were represented: === Country Number United States 139 Canada 28 France 8 Israel 5 West Germany 5 Sweden 4 England 3 Australia 2 Austria 1 Finland 1 Hungary 1 The Netherlands 1 Total 198 === A total of 104 papers were submitted, one fewer than last year, and 34 were accepted. The division by topic, as determined by the program chair, David Dobkin of Princeton, was as follows: === Topic Submitted Accepted Data Structures 13 6 Geometric Algorithms 32 14 Voronoi Diagrams or Hulls 6 2 Triangulation or Decomposition 10 4 Visibility 7 4 Machine Models 3 1 Other 6 3 Motion Planning 13 3 Graphics Algorithms 9 2 Solid Modeling 13 3 Mathematical Bases 12 6 Other 5 0 Very Late or Withdrawn 7 0 Total 104 34 === David also noticed that this conference represented a counterexample to the folk theorem that late papers have the highest acceptance rate: in fact the rate was highest among the first 10 received. At the risk of insulting the unmentioned, permit me to offer a personal summary of the technical highlights of the conference. The most dramatic advance in the field was presented the week before at STOC: Tarjan and Van Wyk developed a linear-time algorithm for triangulating a simple polygon. It has been a long-standing open problem to improve the several O(n logn) algorithms. Their algorithm also can determine whether a polygonal path is simple (non-self-intersecting) in linear time. Based on this fundamental triangulation result, Guibas, Hershberger, Leven, Sharir and Tarjan were able to solve several visibility and shortest-path problems inside simple polygons in linear time. In particular, they presented an O(n) algorithm for computing the edge visibility polygon: the region of a polygon illuminated by a luminescent edge of the polygon. Haussler and Welzl introduced a new technique based on ``epsilon-nets,'' which is in turn based on the Vapnik-Chervonenkis dimension, which leads to improved bounds for the fundamental half-space range query problem. They achieve O(na) query time using O(n) space, where a is smaller than previously established exponents for all dimensions d > 2. Guibas and Seidel developed a method of ``reciprocal search'' that enables them to compute the Minkowski sum of two convex polytopes in three dimensions in time proportional to the size of the inputs plus the size of the output. This sum is fundamental for configuration space motion planning algorithms. Atallah and Goodrich improved previous parallel algorithms, achieving O(logn loglogn) time algorithms, with O(n) processors, for several problems including triangulation of a simple polygon and planar point location. The previous best bounds were O(log2n) time. Devai showed that hidden line elimination can be performed in O(n2) time, which is worst-case optimal, improving over the many O(n2 logn) algorithms. The open problem he listed in the proceedings, achieving the same bound for hidden surface removal, was solved by McKenna before the conference. The distinction between the two problems is that it is easier to determine which edges are visible in a scene than it is to determine which faces are visible. Painting the surfaces requires hidden surface removal. Unfortunately, both Devai's and McKenna's algorithms always use quadratic time, independent of the complexity of the scene, so their algorithms are unlikely to have direct practical significance. Aggarwal, Klawe, Moran, Shor and Wilber presented an algorithm for finding all furthest neighbors for the vertices of a convex polygon in O(n) time, thus settling another long-standing open problem. Only O(n logn) algorithms were known previously. Finally, Fortune presented a novel sweepline algorithm for constructing the Voronoi diagram, overcoming the apparent necessity of knowing sites prior to encountering them with the sweepline by warping the plane. Although worst-case optimal algorithms for this problem have been known for a decade, all are rather complex to implement. Fortune's algorithm seems more straightforward and in addition requires only O(n) space. One result presented on the first day of the conference was improved by the third: Wang and Chan showed that the minimum distance between vertices of two non-intersecting simple polygons that can see one another can be found in O(n logn) time and Aggarwal, Moran, Shor and Suri improved this to O(n) using the same matrix searching algorithm used for the all furthest neighbors problem. Many of the papers presented raised new problems and other problems emerged from conversations. Here are a few that are open at this writing (another personal list), along with their originator or popularizer or just the person who told me (I make no attempt to distinguish these cases). (1) [Fortune] Compute the three-dimensional Voronoi diagram in time proportional to the number of cells k in the diagram, say in O(n logn + k logn) time. The output size is fixed for non-degenerate inputs in two dimensions but can vary from W(n) to W(n2) in three dimensions. (2) [Devai] Perform hidden line elimination (or hidden surface removal) in time proportional to the number of visible edges (or surfaces) k, say in time O(n logn + k), retaining O(n2) performance in the worst case. (3) [Aggarwal] Construct the Voronoi diagram of a simple polygon in linear time. Techniques similar to that of the Aggarwal, Klawe, Moran, Shor and Wilber paper can achieve this for a convex polygon, as Aggarwal and Shor have recently shown, but only O(n logn) algorithms are known for general polygons. (4) [Vijayan] Given a planar graph and a sequence of angles between the adjacent edges incident to each vertex, determine whether there exists a non-crossing straight line embedding of the graph that realizes the given angle sequences. Although special cases have been solved, it is only known that the general problem is decidable. (5) [Sharir] Determine the number of distinct shortest-path edge sequences on the surface of a convex polyhedron. Each such sequence is formed from the labels of the edges crossed by some path that is the shortest path on the surface between its endpoints. Sharir established an upper bound of O(n7), but the best lower bound is W(n2). (6) [Lingas] Determine the complexity of finding a minimum length triangulation of a set of points in the plane. Although the problem is not known to be NP-hard, no polynomial algorithms are available, nor are there suboptimal polynomial algorithms that achieve lengths at most a constant times worse than optimal. (7) [Seidel] Can a finite set of non-intersecting lines in Euclidean space always be rearranged, without two lines ever touching during the rearrangement, so that they all become parallel? (8) [Many people] Prove or disprove: every non-degenerate (trivalent) Delaunay triangulation contains a Hamiltonian cycle. This problem has applications to pattern recognition, which is where I encountered it several years ago. (A weaker version occurred to me: show they do or do not have a perfect matching.) A nearly equivalent version was discussed extensively at the conference, particularly among the mathematicians: does every spherical polytopal graph have a Hamiltonian cycle? A polytopal graph is one that may be realized by the vertices and edges of a three-dimensional convex polytope. A spherical polytopal graph is one that may be realized by the vertices and edges of the convex hull of a set of points on the surface of a sphere (sometimes such graphs are called inscribable). It may not be obvious that there are polytopal graphs that are not spherical, but indeed there are for much the same reason there are triangulation graphs that are not Delaunay. The connection between the two problems is revealed by the transformations of Brown and of Edelsbrunner and Seidel between two-dimensional Delaunay triangulations and three-dimensional convex hulls. The proceedings of the second Symposium on Computational Geometry are available from the ACM Order Department, P. O. Box 64145, Baltimore, MD 21264, order no. 429860, for $19 (members) or $25 (non-members). The third Symposium on Computational Geometry will be held in Waterloo, Ontario, June 810, 1987. Derick Wood is the conference chair and Chee Yap is the program chair. Extended abstracts are due December 15, 1986. Send me your computational geometry news, research announcements and open problems for future columns. ÊU–"computergraphics" style˜Ititle˜!IauthorsšœÏi[œ˜~IbodyšœÎœÜ˜ÇM˜ÊIhorizontalrule•ArtworkClassRule•ArtworkRule˜Itable4šœ˜O˜ØOšœÏbœž˜ N–Rule–Rule˜I pagebreak˜M˜¼N–Rule–Rule˜Ošœ)˜1Ošœó˜óOšžœžœž˜N–Rule–Rule˜M˜ÆMš-œÈœŸœœèœëÐguœœÏgœEœÏmœƒœœœŽÏuœJ¢œ?¢œœËœBœœÅœ˜àMšœæœœ=œX˜‚M˜ Iitemšœhœœœœœa œœ œ¢œ˜•Qšœ‹œœœœ¢œ ˜×Qšœÿœœ,˜±Q˜ÍQš œª¢œ œ¢œ˜ÑQ˜»Q˜¾Q˜• Mšœ#œ˜#œª˜¦Mšf˜f—…—%ì(G