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(n is smaller than previously established exponents for all dimensions d ``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. D evai 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 D evai'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 three dimensions. (2) [D evai] 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 (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. SIGGRAPH'87 Guide for Panels Sara Bly SIGGRAPH'87 Panels Chair PANEL PROPOSALS The panel sessions at the annual SIGGRAPH conference provide alternatives to the technical sessions for presenting information in all areas of computer graphics and interactive techniques. Panel sessions will present interesting techniques and applications in a manner that illustrates different viewpoints or that introduces subject areas not adequately represented elsewhere in the conference. Panel selection will be based on how well the panel session proposes to meet the following criteria: · Covers important and well-focused subject matter · Appeals to a broad audience of computer graphics professionals · Presents new insights or raises new questions for the audience · Provides an effective format for presenting the material PANEL FORMATS The format of the panel is particularly important in presenting the topic in a way that will offer the audience new information, insights or viewpoints. In general, panel formats are encouraged that provide a lively exchange among panel members with very little focus on individual presentations. Panel sessions are not constrained to fit into a predetermined time allocation so that careful consideration can be given to the best method for presenting the information. Following are a few possible ideas for various panel formats. Round table Following the format of ``Face the Nation'' or ``Meet the Press,'' the panel consists of 34 experts in an area of computer graphics discussing issues among themselves. The moderator is responsible for setting forth questions for discussion and for moderating that discussion. Debate The session revolves around the arguments for and against a particular assertion. The format consists of two speakers and a moderator with each speaker having 810 minutes to present opposing sides of a question and 5 minutes rebuttal. After the formal debate, the audience is free to ask questions of the speakers. Controversy The traditional format of a panel is one that presents a controversial look at a subject. The panel is organized around a particular issue or question; 3684 speakers each take 68 minutes to present their differences. The panel members are then open to questions from the panel chair and/or audience. The chair can often encourage the controversy by asking the same question of two or more panelists. Comparison Much like the traditional controversial panel format, the comparison format is focused on a particular topic with 34 panelists representing different viewpoints on that topic but with the emphasis on comparing, rather than arguing, the merits of different techniques. This format encourages each panelist to present the same task to make clear the differences in process or results. A glimpse ahead (or to the side) A panel session may consist of very new material that does not lend itself to a technical paper. The format for such a panel may be an exception to limited individual presentations; speakers are introducing the audience to new work or to a new subject related to computer graphics. Ideas for effective panel sessions Choose a well-focused topic; do not try to cover too broad an area. Clearly identify the particular question or issue that the panel is addressing. Let the panel chair present the context for the panel and moderate the discussion. Choose a chair who can facilitate the panel discussion, summarize views, and ask leading questions. Encourage panelists to state and support assertions. Use examples and visuals to back up individual opinions or facts. Imagine yourself in the audience for the panelWhat will make the panel interesting? What will you learn? PANEL SUBMISSIONS A two-page proposal describing the issues to be discussed and statements from the panelists showing their (possibly opposing) viewpoints should be submitted. A cover sheet with the panel title, the panelists' names and affiliations, and the panel organizer's name, affiliation, address and phone number should be included. Panel members will be asked to agree to publication of their remarks since panel sessions may be recorded and made available for distribution to attendees. Five copies of each panel proposal must be received by Tuesday, January 13, 1987. Acceptance notification will be by March 25, 1987. Send panel submissions to: Sara A. Bly, SIGGRAPH'87 Panels Chair Xerox Corporation 3333 Coyote Hill Road Palo Alto, CA 94304 (415) 858-2890 bly.pa@Xerox.com A panel review committee will read and review each panel proposal. Contributors are invited to discuss panel topics and formats before submitting proposals. Sara Bly, Panels chair, Xerox Corporation Susan Brennan, Hewlett-Packard Labs Glenn Entis, Pacific Data Images Lansing Hatfield, Lawrence Livermore National Laboratory Zuzsanna Molnar, Silicon Graphics Inc. Jean Shuler, Lawrence Livermore National Laboratory ANSI Office and Publishing Systems Standards Activities (X3V1) Technical Committee X3V1, Text: Office and Publishing Systems, has undertaken several new projects: · font and character information interchange standard for typographic quality text, draft by June 1987 · user systems interface, in liason with the Human Factors Society · SGML document interchange format (SDIF), draft by December 1986 To join X3V1 to work on these or any of their more than 30 office systems projects, please contact: Mr. Millard Collins, X3V1 chair IBM Corporation IBM Tower at Williams Square P.O. Box 160960 Irving, TX 75016 (214)556-7690 Interested in Scientific Computer Graphics? Pauline Ores New York University A group of individuals within SIGGRAPH are interested in the use of computer graphics in scientific research and education. Possible functions of an organized group might include: · discussion and presentation of special scientific computer graphic needs and developments, including both software and hardware · information on low-cost methods of producing scientific animation · design concepts applicable to educational scientific animation · database of available animation, images and facilities · information resource for producers of educational materials · presentation of computer graphics at scientific conferences · meetings at the SIGGRAPH conferences To indicate your interest and to receive a notice with the details of the first meeting, please submit your name, address and a short paragraph describing research areas and interests to: Scientific Computer Graphics c/o Pauline Ores New York University Robotics Research Lab 715 Broadway, 12th floor New York, NY 10003 (212) 460-7443