14. Symposium on Computational Geometry 1998: Minneapolis, Minnesota, USA

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, June 7-10, 1998, Minneapolis, Minnesota, USA. ACM Press, 1998, ISBN 0-89791-973-4

Session 1, Applied Track

Victor Milenkovic:
Rotational Polygon Containment and Minimum Enclosure. 1-8
Electronic Edition (ACM DL) BibTeX
Dan Halperin, Jean-Claude Latombe, Randall H. Wilson:
A General Framework for Assembly Planning: The Motion Space Approach. 9-18
Electronic Edition (ACM DL) BibTeX
Jayanth Majhi, Ravi Janardan, Michiel H. M. Smid, Jörg Schwerdt:
Multi-Criteria Geometric Optimization Problems in Layered Manufacturing. 19-28
Electronic Edition (ACM DL) BibTeX
Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, Ka-Po Lam:
Design and Analysis of Planar Shape Deformation. 29-38
Electronic Edition (ACM DL) BibTeX

Session 2, Theoretical Track

Nina Amenta, Marshall W. Bern:
Surface Reconstruction by Voronoi Filtering. 39-48
Electronic Edition (ACM DL) BibTeX
Jack Snoeyink:
Cross-Ratios and Angles Determine a Polygon. 49-57
Electronic Edition (ACM DL) BibTeX
David Eppstein, Jeff Erickson:
Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. 58-67
Electronic Edition (ACM DL) BibTeX
Sergey P. Tarasov, Michael N. Vyalyi:
Construction of Contour Trees in 3D in O(n log n) Steps. 68-75
Electronic Edition (ACM DL) BibTeX

Session 3: Applied and Theoretical Track

Jonathan Richard Shewchuk:
A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations. 76-85
Electronic Edition (ACM DL) BibTeX
Jonathan Richard Shewchuk:
Tetrahedral Mesh Generation by Delaunay Refinement. 86-95
Electronic Edition (ACM DL) BibTeX
Ronald Beirouti, Jack Snoeyink:
Implementations of the LMT Heuristic for Minimum Weight Triangulation. 96-105
Electronic Edition (ACM DL) BibTeX
Olivier Devillers:
Improved Incremental Randomized Delaunay Triangulation. 106-115
Electronic Edition (ACM DL) BibTeX

Session 4: Theoretical Track

Steven Fortune:
Vertex-Rounding a Three-Dimensional Polyhedral Subdivision. 116-125
Electronic Edition (ACM DL) BibTeX
Marcus Vinícius Alvim Andrade, Jorge Stolfi:
Exact Algorithms for Circles on the Sphere. 126-134
Electronic Edition (ACM DL) BibTeX
Alexandra Solan:
Cutting Cylces of Rods in Space. 135-142
Electronic Edition (ACM DL) BibTeX
Alon Efrat, Sariel Har-Peled:
Fly Cheaply: On the Minimum Fuel-Consumption Problem. 143-145
Electronic Edition (ACM DL) BibTeX

Session 5: Applied Track

Lutz Kettner:
Designing a Data Structure for polyhedral Surfaces. 146-154
Electronic Edition (ACM DL) BibTeX
David M. Mount, Nathan S. Netanyahu, Jacqueline Le Moigne:
Improved Algorithms for Robust Point Pattern Matching and Applications to Image Registration. 155-164
Electronic Edition (ACM DL) BibTeX
Hervé Brönnimann, Christoph Burnikel, Sylvain Pion:
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry. 165-174
Electronic Edition (ACM DL) BibTeX
Christoph Burnikel, Stefan Funke, Michael Seel:
Exact Geometric Predicates Using Cascaded Computation. 175-183
Electronic Edition (ACM DL) BibTeX

Session 6: Applied Track

Géza Tóth, Pavel Valtr:
Geometric Graphs with Few Disjoint Edges. 184-191
Electronic Edition (ACM DL) BibTeX
Artur Andrzejak, Boris Aronov, Sariel Har-Peled, Raimund Seidel, Emo Welzl:
Results on k-Sets and j-Facets via Continuous Motion. 192-199
Electronic Edition (ACM DL) BibTeX
Helmut Alt, Stefan Felsner, Ferran Hurtado, Marc Noy:
Point-Sets with few k-Sets. 200-205
Electronic Edition (ACM DL) BibTeX
Alon Efrat, Matthew J. Katz:
On the Union of k-Curved Objects. 206-213
Electronic Edition (ACM DL) BibTeX

Session 7: Applied Track

Fred L. Bookstein:
Features of Deformation Grids: An Approach via Singularity Theory. 214-221
Electronic Edition (ACM DL) BibTeX
Frédéric Cazals:
Effective Nearest Neighbors Searching on the Hyper-Cube, with Applications to Molecular Clustering. 222-230
Electronic Edition (ACM DL) BibTeX
Frank Hoffmann, Klaus Kriegel, Carola Wenk:
Matching 2D Patterns of Protein Spots. 231-239
Electronic Edition (ACM DL) BibTeX
James D. Fix, Richard E. Ladner:
Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons. 240-248
Electronic Edition (ACM DL) BibTeX

Session 8: Theoretical Track

Hervé Brönnimann:
Degenerate Convex Hulls On-Line in Any Fixed Dimension. 249-258
Electronic Edition (ACM DL) BibTeX
Andreas Crauser, Paolo Ferragina, Kurt Mehlhorn, Ulrich Meyer, Edgar A. Ramos:
Randomized External-Memory Algorithms for Some Geometric Problems. 259-268
Electronic Edition (ACM DL) BibTeX
Timothy M. Chan:
Geometric Applications of a Randomized Optimization Technique. 269-278
Electronic Edition (ACM DL) BibTeX
Timothy M. Chan:
On Enumerating and Selecting Distances. 279-286
Electronic Edition (ACM DL) BibTeX

Session 9: Theoretical Track

Therese C. Biedl:
Drawing Planar Partitions I: LL-Drawings and LH-Drawings. 287-296
Electronic Edition (ACM DL) BibTeX
Sunil Arya, Siu-Wing Cheng, David M. Mount:
Approximation Algorithms for Multiple-Tool Miling. 297-306
Electronic Edition (ACM DL) BibTeX
Esther M. Arkin, Joseph S. B. Mitchell, Giri Narasimhan:
Resource-Constrained Geometric Network Optimization. 307-316
Electronic Edition (ACM DL) BibTeX
Gill Barequet, Michael T. Goodrich:
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions. 317-326
Electronic Edition (ACM DL) BibTeX

Session 10: Applied Track

Sariel Har-Peled:
Constructing Cuttings in Theory and Practice. 327-336
Electronic Edition (ACM DL) BibTeX
Marc J. van Kreveld, Tycho Strijk, Alexander Wolff:
Point Set Labeling with Sliding Labels. 337-346
Electronic Edition (ACM DL) BibTeX
Konstantinos G. Kakoulis, Ioannis G. Tollis:
A Unified Approach to Labeling Graphical Features. 347-356
Electronic Edition (ACM DL) BibTeX
Sariel Har-Peled:
An Output Sensitive Algorithm for Discrete Convex Hulls. 357-364
Electronic Edition (ACM DL) BibTeX

Session 11: Theoretical Track

Edward J. Anderson, Sándor P. Fekete:
Asymmetric Rendezvous on the Plane. 365-373
Electronic Edition (ACM DL) BibTeX
Boris Aronov, Mark de Berg, A. Frank van der Stappen, Petr Svestka, Jules Vleugels:
Motion Planning for Multiple Robots. 374-382
Electronic Edition (ACM DL) BibTeX
Sariel Har-Peled:
Constructing Approximate Shortest Path Maps in Three Dimensions. 383-391
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal, Therese C. Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides:
Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract). 392-401
Electronic Edition (ACM DL) BibTeX

Video Review

Kunihiko Sadakane, Hiroshi Imai, Kensuke Onishi, Mary Inaba, Fumihiko Takeuchi, Keiko Imai:
Voronoi Diagrams by Divergences with Additive Weights. 403-404
Electronic Edition (ACM DL) BibTeX
Maria Shneerson, Ayellet Tal:
GASP-II - A Geometric Algorithm Animation System for an Electronic Classroom. 405-406
Electronic Edition (ACM DL) BibTeX
Luiz Velho, Jonas Gomes, Marcos Vinicius Rayol Sobreiro:
Visualization of Color Image Quantization Using Pairwise Clustering. 407-408
Electronic Edition (ACM DL) BibTeX
Felipe Contreras, Jurek Czyzowicz, Eduardo Rivera-Campo, Jorge Urrutia:
Optimal Floodlight Illumination of Stages. 409-410
Electronic Edition (ACM DL) BibTeX
Alejo Hausner, David P. Dobkin:
GAWAIN: Visualizing Geometric Algorithms with Web-Based Animation. 411-412
Electronic Edition (ACM DL) BibTeX
Yiorgos Chrysanthou, Daniel Cohen-Or, Eyal Zadicario:
Viewspace Partitioning of Densely Occluded Scenes. 413-414
Electronic Edition (ACM DL) BibTeX
David P. Dobkin, Emden R. Gansner:
A Path Router for Graph Drawing. 415-416
Electronic Edition (ACM DL) BibTeX