Fourteenth Annual ACM Symposium on Computational Geometry
June 7 - 10, 1998
Minneapolis, Minnesota, USA
Contributed Talks
Sunday, June 7

Session 1, applied track
Chaired by Jarek Rossignac, GVU/Georgia Tech

Rotational Polygon Containment and Minimum Enclosure
Victor J. Milenkovic

A General Framework for Assembly Planning: The Motion Space Approach
Dan Halperin, Jean-Claude Latombe, and Randall H. Wilson

Multi-criteria Geometric Optimization Problems in Layered Manufacturing
Jayanth Majhi, Ravi Janardan, Michiel Smid, and Jörg Schwerdt

Design and Analysis of Planar Shape Deformation
Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, and Ka-Po Lam

Session 2, theoretical track
Chaired by Michiel Smid, Univ. Magdeburg

Surface Reconstruction by Voronoi Filtering
Nina Amenta and Marshall Bern

Cross Ratios and Angles Determine a Polygon
Jack Snoeyink

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a
Data Structure for Finding Pairwise Interactions
David Eppstein and Jeff Erickson

Construction of Contour Trees in 3D in O(n logn) Steps
Sergey P. Tarasov and Michael N. Vyalyi

Monday, June 8

Session 3, applied and theoretical track
Chaired by Steve Fortune, Bell Labs

A Condition Guaranteeing the Existence of Higher-Dimensional
Constrained Delaunay Triangulations
Jonathan Richard Shewchuk

Tetrahedral Mesh Generation by Delaunay Refinement
Jonathan Richard Shewchuk

Implementations of the LMT Heuristic for Minimum Weight Triangulation
Ron Beirouti and Jack Snoeyink

Improved Incremental Randomized Delaunay Triangulation
Olivier Devillers

Session 4, theoretical track
Chaired by Ken Clarkson, Bell Labs

Vertex-Rounding a Three-dimensional Polyhedral Subdivision
Steven Fortune

Exact Algorithms for Circles on the Sphere
Marcus Vinícius A. Andrade and Jorge Stolfi

Cutting Cycles of Rods in Space
Alexandra Solan

Fly Cheaply: On the Minimum Fuel-Consumption Problem
Alon Efrat and Sariel Har-Peled

Session 5, applied track
Chaired by Chris Hoffman, Purdue Univ.

Designing a Data Structure for Polyhedral Surfaces
Lutz Kettner

Improved Algorithms for Robust Point Pattern Matching and Applications
to Image Registration
David M. Mount, Nathan S. Netanyahu, and Jacqueline LeMoigne

Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry
Hervé Brönnimann, Christoph Burnikel, and Sylvain Pion

Exact Arithmetic using Cascaded Computation
Christoph Burnikel, Stefan Funke, and Michael Seel

Session 6, theoretical track
Chaired by Micha Sharir, Tel Aviv Univ.

Geometric Graphs with Few Disjoint Edges
Géza Tóth and Pavel Valtr

Results on k-sets and j-facets via Continuous Motions
Artur Andrzejak , Boris Aronov , Sariel Har-Peled , Raimund Seidel , and Emo Welzl

Point Sets with few k-sets
Helmut Alt, Stefan Felsner, Ferran Hurtado, and Marc Noy

On the Union of kappa-Curved Objects
Alon Efrat and Matthew J. Katz

Tuesday, June 9

Session 7, applied track
Chaired by Jean-Daniel Boissonnat, INRIA

Features of Deformation Grids: An Approach via Singularity Theory
Fred L. Bookstein

Effective Nearest Neighbors Searching on the Hyper-Cube,
with Applications to Molecular Clustering
Frederic Cazals

Matching 2D Patterns of Protein Spots
Frank Hoffmann, Klaus Kriegel, and Carola Wenk

Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons
James D. Fix and Richard E. Ladner

Session 8, theoretical track
Chaired by Mariette Yvinec, CNRS, I3S

Degenerate Convex Hulls On-line in any Fixed Dimension
Hervé Brönnimann

Randomized External-Memory Algorithms for some Geometric Problems
A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. Ramos

Geometric Applications of a Randomized Optimization Technique
Timothy M. Chan

On Enumerating and Selecting Distances
Timothy M. Chan

Session 9, theoretical track
Chaired by John Hershberger, Mentor Graphics

Drawing Planar Partitions I: LL-Drawings and LH-Drawings
Therese C. Biedl

Approximation Algorithms for Multiple-Tool Milling
Sunil Arya, Siu-Wing Cheng, and David M. Mount

Resource-Constrained Geometric Network Optimization
Esther M. Arkin, Joseph S. B. Mitchell, and Giri Narasimhan

Efficiently Approximating Polygonal Paths in Three and Higher Dimensions
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, and Jack Snoeyink

Wednesday, June 10

Session 10, applied track
Chaired by Leo Guibas, Stanford Univ.

Constructing Cuttings in Theory and Practice
Sariel Har-Peled

Point Set Labeling with Sliding Labels
Marc van Kreveld, Tycho Strijk, and Alexander Wolff

A Unified Approach to Labeling Graphical Features
Konstantinos G. Kakoulis and Ioannis G. Tollis

An Output Sensitive Algorithm for Discrete Convex Hulls
Sariel Har-Peled

Session 11, theoretical track
Chaired by Mark Overmars, Utrecht Univ.

Asymmetric Rendezvous on the Plane
Edward J. Anderson and Sándor P. Fekete

Motion Planning for Multiple Robots
Boris Aronov, Mark de Berg, Frank van der Stappen, Peter vestka, and Jules Vleugels

Constructing Approximate Shortest Path Maps in Three Dimensions
Sariel Har-Peled

Curvature-Constrained Shortest Paths in a Convex Polygon
Pankaj Agarwal, Therese C. Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, and Sue Whitesides

Video Review
Chaired by Dan Halperin, Tel Aviv Univ.

Introduction
Dan Halperin

Voronoi Diagram by Divergences with Additive Weights
K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi, and K. Imai

GASP-II - A Geometric Algorithm Animation System for an Electronic Classroom
Maria Shneerson and Ayellet Tal

Visualization of Color Image Quantization using Pairwise Clustering
Luiz Velho, Jonas Gomes, and Marcos V. R. Sobreiro

Optimal Floodlight Illumination of Stages
Felipe Contreras, Jurek Czyzowicz, Eduardo Rivera-Campo, and Jorge Urrutia

Gawain: Visualizing Geometric Algorithms with Web-based Animation
Alejo Hausner and David P. Dobkin

Viewspace Partitioning of Densely Occluded Scenes
Yiorgos Chrysanthou, Daniel Cohen-Or, and Eyal Zadicario

A Path Router for Graph Drawing
David P. Dobkin, Emden R. Gansner, Eleftherios Koutsofios, and Stephen C. North