The program consisted of 3 invited speakers, 41 technical papers, 6 videos in the fourth annual Video Review, and, a new feature this year, 18 two-page communications that were presented as posters or demos at the conference. Also new for this year were conference T-shirts: they showed the breadth of application of geometric computation by displaying two dozen figures from accepted papers and communications.

- Work in these areas ranges from theoretical to the applied, and sometimes mixes the two. To take "convex polytopes" as an example: Gritzmann & Hufnagel (U Trier) give a theoretical answer to the "Minkowski reconstruction" problem that arises in computer vision, Chan (UBC) gives simple and beautiful algorithms for 2-D and 3-D output-sensitive convex hull computation as a result of general theoretical work, and Avis & Bremner (McGill) give an insightful study of convex hull algorithm performance, especially for degenerate inputs.
- Voronoi diagrams are studied for curves by Alt (FU Berlin) & Schwarzkopf (Utrecht), for polygonal distance functions by Abellanas, Hernandez (U Poli. Madrid), Klein (FernU Hagen), Neumann-Lara (U Nac. Aut. Mexico), Urrutia (U Ottawa) and for polyhedral distance functions by Boissonnat, Yvinec (INRIA), Sharir & Tagansky (Tel Aviv) Related is a study of Delaunay triangulation algorithms in the plane Su (Transarc) & Drysdale (Dartmouth); Minimum-weight and other triangulations are also studied by Dickerson, Montague (Middlebury) & McElfresh (Dartmouth) and by Aichholzer, Aurenhammer, Taschwer & Rote (Technische U Graz).
- Arrangements continue to be a fruitful area of study for bounds on substructure complexity, Tagansky (Tel Aviv); on envelopes, Agarwal (Duke), Schwarzkopf (Utrecht) & Sharir (Tel Aviv); and on levels, Agarwal (Duke), Efrat & Sharir (Tel Aviv). Also considered is robust implementation by Guibas (Stanford) & Marimont (Xerox PARC).
- Shortest path variations are studied: precision-sensitive in 3D by Choi, Yap (Courant) & Sellen (Saarlandes); network approximations by Mata & Mitchell (SUNY SB); approximate path queries among rectangles by Chen, Klenk (Notre Dame) & Tu (Taiwan), paths among rectangular prisms in 3D, Choi & Yap (Courant).
- New and improved data structures and algorithms for geometric searching problems are given for closest pair maintenance, Bespamyatnikh (Ural State); rectangle enclosure and point-dominance, Gupta, Janardan, Dasgupta (Minn) & Smid (MPI Inf), and approximate range searching Arya (MPI Inf) & Mount (UMD). Arya (MPI Inf), Mount (UMD), and Narayan (Harvard) also tried to analyze boundary effects in nearest neighbor search structures.
- Combinatorial work includes exciting lower bounds for Hopcroft's problem by Erickson (UC Berkeley), Helly-type theorems by Matousek (Prague), progress on Conway's thrackle conjecture by Lovasz (Yale), Pach (Courant) & Szegedy (AT&T Bell Labs), cutting pseudo-parabolas by Tamaki & Tokuyama (IBM Tokyo), and stabbing with lines Agarwal (Duke), Aronov (Polytech, NY) & Suri (St. Louis).
- Optimization problems are considered by Icking & Klein (FernU Hagen) -- searching for the kernel of a polygon; by Agarwal (Duke) & Sharir (Tel Aviv) -- randomized algorithms for width, etc; and by Dyer (Leeds) -- parallel linear programming. Rege (UC Berkeley) considers a practical algorithm for geometric theorem proving.
- GIS applications motivated four papers: cartograms, Edelsbrunner & Waupotitsch (UIUC); map labeling, Wagner & Wolff (FU Berlin); subdivision overlay, Finke & Hinrichs (WWU Muenster); optimal segment intersection, Balaban (Russian Acad Sci).
- Graphics has another four: approximating form factors, Pellegrini (Kings), polyhedral surface decomposition, Chazelle, Dobkin, Shouraboura & Tal (Princeton); graph drawing, Di Battista (Basilicata), Garg, Tamassia (Brown), Liotta, Tassinari & Vargiu (U di Roma); reflections, Aronov (Polytech, NY), Davis (St. John's), Dey, Pal & Prasad (IIT Kharagpur)
- Robotics applications include fixturing by Overmars, Rao, Schwarzkopf & Wentink (Utrecht); collision detection for a rotating polyhedron by Schoemer (Saarlandes) & Thiel (MPI Inf); and representation of visibility graphs by Pocchiola (Ecole Norm. Sup.) & Vegter (Groningen).

Unlike my experiences at other conferences, people actually talked to the poster and demo presenters. In fact, everyone I asked thought that the posters/demos were a good idea and several people said that they would be submitting communications for the 1996 conference.

Jack Snoeyink

Dept. Computer Science

University of British Columbia

Go to Home page for Jack, UBC CS, Imager, or IAM