11th Annual ACM Symposium on Computational Geometry
June 5-7, Vancouver, British Columbia, Canada
Contains:
Conference Program,
communications,
videos, and
invited talks
Also available: Registration
info, and Registration
Fill-Out Form
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
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
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
Communications are two page reports in the proceedings, primarily on
experimental results, experiences with real-world applications, and
other practical issues that are relevant to computational geometry.
They will be presented as posters, possibly with implementation demos.
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 video review showcases advances in the use of algorithm animation,
visualization, and interactive computing in the study of computational
geometry. The video review tape is distributed to all registrants at the
conference and will subsequently be available from ACM.
- 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
See the program for times and rooms
acm-scg@cs.ubc.ca