Conference Program

Sunday, June 3, 1995

• 7:00-10:00PM Reception (& Registration) I. MacInnes Lounge, Gage Residences

Monday, June 5, 1995

• 8:30 Registration, Coffee: Angus 104
• 8:40 Opening Remarks: Angus 104

Session 1: 8:50-9:50 chair: Raimund Seidel U des Saarlandes; UC Berkeley

• 8:50 A Polynomial Time Algorithm for Minkowski Reconstruction, Peter Gritzmann, Alexander Hufnagel U Trier
• 9:10 Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems, Timothy M. Y. Chan UBC, Vancouver
• 9:30 How Good are Convex Hull Algorithms?, David Avis, David Bremner McGill U
• 9:50 Coffee Break
• 10:10 Invited Talk: Computational Geography, Michael Goodchild NCGIA; UC Santa Barbara

Session 2: 11:00-12:00 chair: Danny Halperin Stanford U

• 11:00 Immobilizing Polygons against a Wall, Mark Overmars, Anil Rao, Otfried Schwarzkopf, Chantal Wentink Utrecht U
• 11:20 Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, Pankaj K. Agarwal Duke U, Alon Efrat, Micha Sharir Tel Aviv U; Courant
• 11:40 Efficient Collision Detection for Moving Polyhedra, Elmar Schomer U des Saarlandes, Christian Thiel MPI Informatik, Saarbrucken
• 12:00 Lunch: Trekkers

Session 3: 1:40-3:00 chair: Mark de Berg Utrecht U

• 1:40 A Comparison of Sequential Delaunay Triangulation Algorithms, Peter Su Transarc Corp., Robert L. Scot Drysdale Dartmouth Col
• 2:00 Voronoi Diagrams and Containment of Families of Convex Sets on the Plane, M. Abellanas, G. Hernandez U Poli. Madrid, Rolf Klein FernU Hagen, V. Neumann-Lara U Nac. Aut. Mexico, Jorge Urrutia U Ottawa
• 2:20 Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions, Jean- Daniel Boissonnat INRIA Sophia Antipolis, Micha Sharir, Boaz Tagansky Tel Aviv U, Mariette Yvinec INRIA Sophia Antipolis and CNRS
• 2:40 The Voronoi Diagram of Curved Objects, H. Alt Freie U Berlin, O. Schwarzkopf Utrecht U
• 3:00 Coffee Break: Angus 217
• 3:20 Poster Session: Angus 217

Session 4: 4:10-5:10 chair: Michael Goodrich Johns Hopkins

• 4:10 A Combinatorial Approach to Cartograms, H. Edelsbrunner, R. Waupotitsch UI Urbana-Champaign
• 4:30 Map Labeling Heuristics: Provably Good and Practically Useful, Frank Wagner, Alexander Wolff Freie U Berlin
• 4:50 Overlaying simply connected planar subdivisions in linear time, U. Finke, K. Hinrichs WWU Munster
• 5:30 Salmon Barbeque: SUB playing field

Tuesday, June 6, 1995

• 8:40 Coffee: Angus 217

Session 5: 8:50-9:50 chair: Emo Welzl Freie U Berlin

• 8:50 New Lower Bounds for Hopcroft's Problem, Jeff Erickson UC Berkeley
• 9:10 A Helly-type Theorem for Unions of Convex Sets, Jiri Matousek Charles U, Prague
• 9:30 On Conway's Thrackle Conjecture, Laszlo Lovasz Yale U, Janos Pach CUNY; Courant, Mario Szegedy AT&T Bell Labs
• 9:50 Coffee Break: Angus 217
• 10:10 Poster Session: Angus 217

Session 6: 11:00-12:00 chair: Hiroshi Imai Tokyo U

• 11:00 An Optimal Algorithm for Closest Pair Maintenance, Sergei N. Bespamyatnikh Ural State U
• 11:20 The Rectangle Enclosure and Point-Dominance Problems Revisited, P. Gupta, R. Janardan U of Minn., M. Smid MPI Informatik, Saarbrucken, Bhaskar Dasgupta U of Minn.
• 11:40 Approximate Range Searching, S. Arya MPI Informatik, Saarbrucken, D. Mount UMD, Col. Park
• 12:00 Lunch: Trekkers
• 1:40 Invited Talk: Prediction, Data Compression, and Metric Dimension, David Haussler UC Santa Cruz

Session 7: 2:30-3:30 chair: David Eppstein UC Irvine

• 2:30 The Overlay of Lower Envelopes in Three Dimension and its Applications, Pankaj K. Agarwal Duke U, Otfried Schwarzkopf Utrecht U, Micha Sharir Tel Aviv U; Courant
• 2:50 Rounding Arrangements Dynamically, L. Guibas Stanford U, D. Marimont Xerox PARC
• 3:10 A New Technique for Analyzing Substructures in Arrangements, Boaz Tagansky Tel Aviv U
• 3:30 Coffee Break: Angus 217

Session 8: 3:50-5:10 chair: Monique Teillaud INRIA Sophia Antipolis

• 3:50 An Optimal Algorithm for Finding Segments Intersections, Ivan J. Balaban Russian Acad Sci
• 4:10 Triangulations Intersect Nicely, Oswin Aichholzer, Franz Aurenhammer, Michael Taschwer, Gunter Rote Technische U Graz
• 4:30 How to Cut Pseudo-Parabolas into Segments, H. Tamaki, T. Tokuyama IBM Tokyo Res. Lab
• 4:50 New Algorithms and Empirical Findings on Minimum Weight Triangulation Heuristics, M. T. Dickerson Middlebury Col, S. A. McElfresh Dartmouth Col, M. Montague Middlebury Col
• 5:20 Business Meeting: CICSR/CS Atrium

Wednesday, June 7, 1995

• 8:40 Coffee: Angus 217

Session 9: 8:50-9:50 chair: Danny Halperin Stanford U

• 8:50 Computing the Visibility Graph via Pseudo-triangulation, Michel Pocchiola Ecole Norm. Sup., Gert Vegter Groningen U
• 9:10 Searching for the Kernel of a Polygon - A Competitive Strategy, Christian Icking, Rolf Klein FernU Hagen
• 9:30 Line Stabbing Bounds in Three Dimensions, Pankaj K. Agarwal Duke U, Boris Aronov Polytechnic U, NY, and Subhash Suri Washington U, St. Louis
• 9:50 A Complete and Practical Algorithm for Geometric Theorem Proving, A. Rege UC Berkeley
• 10:10 Coffee Break: Angus 217

Session 10: 10:40-12:00 chair: Michael Goodrich Johns Hopkins

• 10:40 Monte Carlo Approximation of Form Factors with Error Bounded a Priori, Marco Pellegrini Kings Col, London
• 11:00 Strategies for Polyhedral Surface Decomposition: An Experimental Study, Bernard Chazelle, David P. Dobkin, Nadia Shouraboura, Ayellet Tal Princeton U
• 11:20 An Experimental Comparison of Three Graph Drawing Algorithms, Giuseppe Di Battista U della Basilicata, Ashim Garg Brown U, Giuseppe Liotta U di Roma, Roberto Tamassia Brown U, Emanuele Tassinari, Francesco Vargiu U di Roma
• 11:40 Visibility with Reflection, Boris Aronov Polytechnic U, NY, Alan R. Davis St. John's U, Tamal K. Dey, Sudebkumar P. Pal, D. Chithra Prasad IIT Kharagpur
• 12:00 Lunch: Trekkers
• 1:40 Invited Talk: Geometric Algorithms and the Rendering Equation, Pat Hanrahan Stanford U

Session 11: 2:30-3:30 chair: Seth Teller M.I.T.

• 2:30 Efficient Randomized Algorithms for Some Geometric Optimization Problems, Pankaj K. Agarwal Duke U, Micha Sharir Tel Aviv U; Courant
• 2:50 Accounting for Boundary Effects in Nearest Neighbor Searching, Sunil Arya MPI Informatik, Saarbrucken, David Mount UMD, Col. Park, Onuttom Narayan Harvard U
• 3:10 A Parallel Algorithm for Linear Programming in Fixed Dimension, Martin Dyer U of Leeds
• 3:30 Coffee Break: Angus 217

Session 12: 3:50-4:50 chair: Mark de Berg Utrecht U

• 3:50 Precision-Sensitive Euclidean Shortest Path in 3-Space, Joonsoo Choi Courant, Jurgen Sellen U des Saarlandes, Chee-Keng Yap Courant
• 4:10 Approximation Algorithms for Geometric Tour and Network Design Problems, Christian Mata, Joseph S.B. Mitchell SUNY Stony Brook
• 4:30 Shortest Path Queries among Weighted Obstacles in the Rectilinear Plane, Danny Z. Chen, Kevin S. Klenk U of Notre Dame, Hung-Yi T. Tu Providence U, Taiwan
• 4:50 Rectilinear Geodesics in 3-Space, Joonsoo Choi, Chee-Keng Yap Courant

Representation/Modelling in 3-D:

• Union of Spheres (UoS) Model for Volumetric Data, Vishwa Ranjan, Alain Fournier UBC, Vancouver
• Hexahedral Mesh Generation via the Dual, Steven Benzley Bringham Young U, Ted D. Blacker, Scott A. Mitchell Sandia National Labs, Peter Murdoch Bringham Young U, Timothy J. Tautges Sandia National Labs
• Fast and Robust Computation of Molecular Surfaces, Michel F. Sanner, Arthur J. Olson Scripps Res Inst, La Jolla, Jean-Claude Spehner U de Haute Alsace
• Representation and Computation of Boolean Combinations of Sculptured Models, Shankar Krishnan, Atul Narkhede, Dinesh Manocha UNC Chapel Hill

Visualizing

• The Extendible Drawing Editor Ipe, Otfried Schwarzkopf Utrecht U
• Geomview: A System for Geometric Visualization, T. Munzner, S. Levy, M. Philips The Geometry Center, Minn.
• A 2-D Visualizer for Computational Geometry, Robert R. Lewis UBC, Vancouver

Exact Computation

• Evaluating signs of determinants using single-precision arithmetic, Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, INRIA Sophia Antipolis, Franco P. Preparata Brown U, Mariette Yvinec INRIA Sophia Antipolis & CNRS
• Exact Geometric Computation in LEDA, Christoph Burnikel, Jochen Konnemann, Kurt Mehlhorn, Stefan Naher, Stefan Schirra, Christian Uhrig MPI Informatik, Saarbrucken

Robotics

• A Global Motion Planner for a Mobile Robot on a Terrain, Jean-Daniel Boissonnat INRIA Sophia Antipolis, Katrin Dobrindt Utrecht U, Bernhard Geiger INRIA Sophia Antipolis, Henri Michel CRS4, Cagliari
• Complete Algorithms for Reorienting Polyhedral Parts Using a Pivoting Gripper, Anil Rao Utrecht U, David Kriegman Yale U, Ken Goldberg USC

Geographic Information Systems

• Geometry in GIS is not Combinatorial: Segment Intersection for Polygon Overlay, D. S. Andrews, J. Snoeyink UBC
• On Levels of Detail in Terrains, Mark de Berg, Katrin Dobrindt Utrecht U

Wire Routing

• An Animated Library of Combinatorial VLSI-Routing Algorithms, Dorothea Wagner, Karsten Weihe U Konstanz
• Printed Circuit Board Simplification: Simplifying Subdivisions in Practice, Marc van Kreveld, Berto van de Kraats, Mark Overmars Utrecht U

Applications of Polygons

• An Implementation for Maintaining Arrangements of Polygons, Michael Goldwasser Stanford U
• Minimal Enclosing Parallelogram with Application, Christian Schwarz MPI Informatik, Saarbrucken, Jurgen Teich ETH Zurich, Alek Vainshtein Tel Aviv U, Emo Welzl Freie U Berlin, Brian L. Evans UC Berkeley
• Topologically Sweeping the Visibility Complex of Polygonal Scenes, Stephane Riviere iMAGIS-IMAG, Grenoble

• The Visibility Complex Made Visibly Simple, Fredo Durand, Claude Puech iMAGIS-IMAG, Grenoble
• An Animation of Euclid's Proposition 47: The Pythagorean Theorem, Steve Glassman, Greg Nelson DEC SRC
• HIPAIR: Interactive Mechanism Analysis, Design Using Configuration Spaces, L. Joskowitz IBM, E. Sacks Purdue
• Incremental Collision Detection for Polygonal Models, M. K. Ponamgi, M. C. Lin, D. Manocha UNC Chapel Hill
• Convex Surface Decomposition, Bernard Chazelle, David P. Dobkin, Nadia Shouraboura, Ayellet Tal Princeton U
• 3D Modeling Using the Delaunay Triangulation, Bernhard Geiger INRIA Sophia Antipolis

• Monday: Computational Geography, Michael Goodchild NCGIA; UC Santa Barbara
• Tuesday: Prediction, Data Compression, and Metric Dimension, David Haussler UC Santa Cruz
• Wednesday: Geometric Algorithms and the Rendering Equation, Pat Hanrahan Stanford U