Schedule of Events

14th Annual ACM Symposium on

COMPUTATIONAL GEOMETRY

June 7-10, 1998

Minneapolis, Minnesota

All events are at the Radisson Metrodome Hotel.

Saturday, June 6

19:00--22:00
Reception and Registration

Sunday, June 7

09:00
Registration re-opens

10:30
Welcoming Remarks
Jarek Rossignac (GVU/Georgia Tech) Ken Clarkson (Bell Labs) ;

Session 1: Applied Track
Chair: Jarek Rossignac, GVU/Georgia Tech

10:40
Rotational Polygon Containment and Minimum Enclosure
Victor J. Milenkovic (Univ. of Miami)

11:00
A General Framework for Assembly Planning: The Motion Space Approach
Dan Halperin (Tel Aviv Univ.) ; Jean-Claude Latombe, Randall H. Wilson (Stanford Univ.)

11:20
Multi-criteria Geometric Optimization Problems in Layered Manufacturing
Jayanth Majhi, Ravi Janardan (Univ. of Minnesota) ; Michiel Smid, Jörg Schwerdt (Univ. of Magdeburg)

11:40
Design and Analysis of Planar Shape Deformation
Siu-Wing Cheng (Hong Kong Univ. of Science and Technology) ; Herbert Edelsbrunner (Univ. of Illinois at Urbana-Champaign and Raindrop Geomagic) ; Ping Fu (Raindrop Geomagic, Inc. and NCSA, Univ. of Illinois) ; Ka-Po Lam (Hong Kong Univ. of Science and Technology)

12:00--13:30
Lunch

13:30--14:30
Invited Talk 1
Shape Space from Deformation

Herbert Edelsbrunner (Univ. of Illinois at Urbana-Champaign and Raindrop Geomagic)
Abstract --- Speaker

Session 2: Theoretical Track
Chair: Michiel Smid, Univ. Magdeburg

14:40
Surface Reconstruction by Voronoi Filtering
Nina Amenta (Univ. of Texas, Austin) ; Marshall Bern (Xerox PARC)

15:00
Cross Ratios and Angles Determine a Polygon
Jack Snoeyink (INRIA & Univ. of British Columbia)

15:20
Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions
David Eppstein (Univ. of California, Irvine) ; Jeff Erickson (Duke Univ.)

15:40
Construction of Contour Trees in 3D in
O(n logn) steps

Sergey P. Tarasov, Michael N. Vyalyi (Russian Academy of Science, Computing Center)

16:00--16:30
Coffee Break

16:30--17:30
Invited Talk 2
Computational Geometry Issues of Statistical Depth

Peter Rousseeuw (Univ. of Antwerp)
Abstract ---Speaker

20:30--22:30
Business Meeting

Monday, June 8

Session 3: Applied and Theoretical Track
Chair: Steve Fortune, Bell Labs

08:50
A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations
Jonathan Richard Shewchuk (Carnegie Mellon Univ.)

09:10
Tetrahedral Mesh Generation by Delaunay Refinement
Jonathan Richard Shewchuk (Carnegie Mellon Univ.)

09:30
Implementations of the LMT Heuristic for Minimum Weight Triangulation
Ron Beirouti (Univ. of British Columbia) ; Jack Snoeyink (INRIA & Univ. of British Columbia)

09:50
Improved Incremental Randomized Delaunay Triangulation
Olivier Devillers (INRIA
Sophia-Antipolis)

10:10--10:40
Coffee Break

Session 4: Theoretical Track
Chair: Ken Clarkson, Bell Labs

10:40
Vertex-Rounding a Three-dimensional Polyhedral Subdivision
Steven Fortune (Bell Laboratories, Lucent Technologies)

11:00
Exact Algorithms for Circles on the Sphere
Marcus Vinícius A. Andrade (Univ. of Viçosa) ; Jorge Stolfi (Univ. of Campinas)

11:20
Cutting Cycles of Rods in Space
Alexandra Solan (Tel-Aviv Univ.)

11:40
Fly Cheaply: On the Minimum Fuel-Consumption Problem
Alon Efrat, Sariel Har-Peled (Tel-Aviv Univ.)

12:00--13:30
Lunch

13:30--14:30
Invited Talk 1
Applications of Level Set and Fast Marching Methods to Problems in Computational Geometry

James Sethian (Univ. of California, Berkeley)
Abstract---Speaker

Session 5: Applied Track
Chair: Leonidas Guibas, Stanford Univ.

14:40
Designing a Data Structure for Polyhedral Surfaces
Lutz Kettner (ETH Zürich)

15:00
Improved Algorithms for Robust Point Pattern Matching and Applications to Image Registration
David M. Mount (Univ. of Maryland) ; Nathan S. Netanyahu (Univ. of Maryland and NASA Goddard Space Flight Center) ; Jacqueline LeMoigne (Universities Space Research Association)

15:20
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry
Hervé Brönnimann (INRIA Sophia-Antipolis) ; Christoph Burnikel (Max-Planck-Institut für Informatik) ; Sylvain Pion (INRIA Sophia-Antipolis)

15:40
Exact Arithmetic using Cascaded Computation
Christoph Burnikel, Stefan Funke, Michael Seel (Max-Planck-Institut für Informatik)

16:00--16:30
Coffee Break

Session 6: Theoretical Track
Chair: Micha Sharir, Tel Aviv Univ.

16:30
Geometric Graphs with Few Disjoint Edges
Géza Tóth (Courant Institute, NYU and DIMACS Center, Rutgers Univ.) ; Pavel Valtr (Charles Univ., Prague and DIMACS Center, Rutgers Univ.)

16:50
Results on k-sets and j-facets via Continuous Motions
Artur Andrzejak (ETH Zürich) ; Boris Aronov (Polytechnic Univ., Brooklyn) ; Sariel Har-Peled (Tel-Aviv Univ.) ; Raimund Seidel (Univ. des Saarlandes) ; Emo Welzl (ETH Zürich)

17:10
Point Sets with few k-sets
Helmut Alt, Stefan Felsner (Freie Universität Berlin) ; Ferran Hurtado, Marc Noy (Departament de Matemática Aplicada II)

17:30
On the Union of k-Curved Objects
Alon Efrat (Tel-Aviv Univ.) ; Matthew J. Katz (Ben-Gurion Univ.)

19:00--21:30
Conference Dinner and After-Dinner Talk

20:30--21:30
Invited Talk 4
The Art and Mathematics of Geometric Dissections

Greg Frederickson (Purdue Univ.)
Abstract---Speaker

Tuesday, June 9

Session 7: Applied Track
Chair: Fred Bookstein, Univ. of Michigan

08:50
Features of Deformation Grids: An Approach via Singularity Theory
Fred L. Bookstein (Univ. of Michigan)

09:10
Effective Nearest Neighbors Searching on the Hyper-Cube, with Applications to Molecular Clustering
Frederic Cazals (INRIA)

09:30
Matching 2D Patterns of Protein Spots
Frank Hoffmann, Klaus Kriegel, Carola Wenk (Freie Universität Berlin)

09:50
Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons
James D. Fix, Richard E. Ladner (Univ. of Washington)

10:10--10:40
Coffee Break

Session 8: Theoretical Track
Chair: Mariette Yvinec, CNRS, I3S

10:40
Degenerate Convex Hulls On-line in any Fixed Dimension
Hervé Brönnimann (INRIA Sophia-Antipolis)

11:00
Randomized External-Memory Algorithms for some Geometric Problems
A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, E. Ramos (Max-Planck-Institut für Informatik)

11:20
Geometric Applications of a Randomized Optimization Technique
Timothy M. Chan (Univ. of Miami)

11:40
On Enumerating and Selecting Distances
Timothy M. Chan (Univ. of Miami)

12:00--13:30
Lunch

13:30--14:30
Invited Talk 5
Progressive Representations for Geometry

Hugues Hoppe (Microsoft)
Abstract---Speaker

Session 9: Theoretical Track
Chair: John Hershberger, Mentor Graphics

14:40
Drawing Planar Partitions I: LL-Drawings and LH-Drawings
Therese C. Biedl (McGill Univ.)

15:00
Approximation Algorithms for Multiple-Tool Milling
Sunil Arya (Hong Kong Univ. of Science & Technology) ; Siu-Wing Cheng (Hong Kong Univ. of Science and Technology) ; David M. Mount (Univ. of Maryland)

15:20
Resource-Constrained Geometric Network Optimization
Esther M. Arkin, Joseph S. B. Mitchell (State Univ. of New York, Stony Brook) ; Giri Narasimhan (Univ. of Memphis)

15:40
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions
Gill Barequet (Johns Hopkins Univ.) ; Danny Z. Chen, Ovidiu Daescu (Univ. of Notre Dame) ; Michael T. Goodrich (Johns Hopkins Univ.) ; Jack Snoeyink (INRIA & Univ. of British Columbia)

16:00--16:30
Coffee Break

16:30--17:50
Panel Discussion
``The Theory/Application Interface''
Steven Fortune (Moderator) (Bell Laboratories, Lucent Technologies)
Mark Overmars (Utrecht Univ.)
Jean Ponce (Univ. of Illinois)
Jarek Rossignac (GVU/Georgia Tech)
Peter Rousseeuw (Univ. of Antwerp)
Steve Vavasis (Cornell Univ.)

20:00--20:45
Computational Geometry with CGAL and LEDA
Hervé Brönnimann (INRIA Sophia-Antipolis)
Stefan Schirra (Max-Planck-Institut für Informatik)
Abstract

21:00--22:30
Problem Session
Coordinator: Pankaj Agarwal (Duke Univ.)

Wednesday, June 10

09:10--10:10
Invited Talk 6
Algorithms in Real Algebraic Geometry

Richard Pollack (Courant Institute, New York Univ.)
Abstract---Speaker

10:10--10:40
Coffee Break

Session 10: Applied Track
Chair: Tamal Dey, I.I.T. Kharagpur

10:40
Constructing Cuttings in Theory and Practice
Sariel Har-Peled (Tel-Aviv Univ.)

11:00
Point Set Labeling with Sliding Labels
Marc van Kreveld, Tycho Strijk (Utrecht Univ.) ; Alexander Wolff (Freie Universität Berlin)

11:20
A Unified Approach to Labeling Graphical Features
Konstantinos G. Kakoulis, Ioannis G. Tollis (The Univ. of Texas at Dallas)

11:40
An Output Sensitive Algorithm for Discrete Convex Hulls
Sariel Har-Peled (Tel-Aviv Univ.)

12:00--13:30
Lunch

Session 11: Theoretical Track
Chair: Mark Overmars, Utrecht Univ.

13:30
Asymmetric Rendezvous on the Plane
Edward J. Anderson (Univ. of New South Wales) ; Sándor P. Fekete (Universität zu Köln)

13:50
Motion Planning for Multiple Robots
Boris Aronov (Polytechnic Univ., Brooklyn) ; Mark de Berg, Frank van der Stappen (Utrecht Univ.) ; Peter vestka (CWI) ; Jules Vleugels (Utrecht Univ.)

14:10
Constructing Approximate Shortest Path Maps in Three Dimensions Sariel Har-Peled (Tel-Aviv Univ.)

14:30
Curvature-Constrained Shortest Paths in a Convex Polygon
Pankaj Agarwal (Duke Univ.) ; Therese C. Biedl, Sylvain Lazard, Steve Robbins (McGill Univ.) ; Subhash Suri (Washington Univ.) ; Sue Whitesides (McGill Univ.)

14:50
Adjourn

VIDEO REVIEW
Chair: Dan Halperin, Tel Aviv Univ.

  • Voronoi Diagram by Divergences with Additive Weights
    K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi (Univ. of Tokyo) ; K. Imai (Chuo Univ.)

  • GASP-II - A Geometric Algorithm Animation System for an Electronic Classroom
    Maria Shneerson (The Weizmann Institute of Science) ; Ayellet Tal (Technion - Israel Institute of Technology)

  • Visualization of Color Image Quantization using Pairwise Clustering
    Luiz Velho, Jonas Gomes (IMPA - Instituto de Matemática Pura e Aplicada) ; Marcos V. R. Sobreiro (PUC-Rio)

  • Optimal Floodlight Illumination of Stages
    Felipe Contreras (Univ. of Ottawa) ; Jurek Czyzowicz (Université du Quebec à Hull) ; Eduardo Rivera-Campo (Univ. Autonóma Metropolitana-I) ; Jorge Urrutia (Univ. of Ottawa)

  • Gawain: Visualizing Geometric Algorithms with Web-based Animation
    Alejo Hausner, David P. Dobkin (Princeton Univ.)

  • Viewspace Partitioning of Densely Occluded Scenes
    Yiorgos Chrysanthou (Univ. College London) ; Daniel Cohen-Or, Eyal Zadicario (Tel-Aviv Univ.)

  • A Path Router for Graph Drawing
    David P. Dobkin (Princeton Univ.) ; Emden R. Gansner,
    Eleftherios Koutsofios, Stephen C. North (AT&T Laboratories)