5. Symposium on Computational Geometry 1989: Saarbrücken, Germany

Proceedings of the Fifth Annual Symposium on Computational Geometry, June 5-7, 1989, Saarbrüchen, Germany. ACM Press, 1989, ISBN 0-89791-318-3

Session 1

Jirí Matousek:
Construction of epsilon Nets. 1-10
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal:
A Deterministic Algorithm for Partitioning Arrangements of Lines and Its Application. 11-22
Electronic Edition (ACM DL) BibTeX
Mike Paterson, F. Frances Yao:
Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. 23-32
Electronic Edition (ACM DL) BibTeX
Ketan Mulmuley:
A Fast Planar Partition Algorithm, II. 33-43
Electronic Edition (ACM DL) BibTeX
Peter W. Shor, Christopher J. Van Wyk:
Detecting and Decomposing Self-Overlapping Curves. 44-50
Electronic Edition (ACM DL) BibTeX
Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis:
Area Requirement and Symmetry Display in Drawing Graphs. 51-60
Electronic Edition (ACM DL) BibTeX
Gert Vegter:
Kink-Free Deformations of Polygons. 61-68
Electronic Edition (ACM DL) BibTeX
Yan Ke:
An Efficient Algorithm for Link-Distance Problems. 69-78
Electronic Edition (ACM DL) BibTeX

Erich Kaltofen:
Computing the Irreducible Real Factors and Components of an Algebraic Curve. 79-87
Electronic Edition (ACM DL) BibTeX
Shreeram S. Abhyankar, Srinivasan Chandrasekar, Vijaya Chandru:
Degree Complexity Bounds on the Intersection of Algebraic Curves. 88-93
Electronic Edition (ACM DL) BibTeX
Chandrajit L. Bajaj, Insung Ihm:
Hermite Interpolation of Rational Space Curves Using Real Algebraic Surfaces. 94-103
Electronic Edition (ACM DL) BibTeX
Mikhail J. Atallah, Jyh-Jong Tsay:
On the Parallel Decomposability of Geometric Problems. 104-113
Electronic Edition (ACM DL) BibTeX
Mikhail J. Atallah, Danny Z. Chen:
Optimal Parallel Algorithm for Visibility of a Simple Polygon from a Point. 114-123
Electronic Edition (ACM DL) BibTeX

Jirí Matousek, Emo Welzl:
Good Splitters for Counting Points in Triangles. 124-130
Electronic Edition (ACM DL) BibTeX
Bernard Chazelle, Burton Rosenberg:
Computing Partial Sums in Multidimensional Arrays. 131-139
Electronic Edition (ACM DL) BibTeX
Imre Bárány, Zoltán Füredi, László Lovász:
On the Number of Halving Planes. 140-144
Electronic Edition (ACM DL) BibTeX
Herbert Edelsbrunner:
An Acyclicity Theorem for Cell Complexes in d Dimensions. 145-151
Electronic Edition (ACM DL) BibTeX
Richard Pollack, Rephael Wenger:
Necessary and Sufficient Conditions for Hyperplane Transversals. 152-155
Electronic Edition (ACM DL) BibTeX

Dan Halperin, Mark H. Overmars:
Efficient Motion Planning for an L-Shaped Object. 156-166
Electronic Edition (ACM DL) BibTeX
L. Paul Chew, Klara Kedem:
Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles. 167-173
Electronic Edition (ACM DL) BibTeX
Joseph Friedman, John Hershberger, Jack Snoeyink:
Compliant Motion in a Simple Polygon. 175-186
Electronic Edition (ACM DL) BibTeX
Amy J. Briggs:
An Efficient Algorithm for One-Step Planar Complaint Motion Planning with Uncertainty. 187-196
Electronic Edition (ACM DL) BibTeX

Victor Milenkovic:
Calculating Approximate Curve Arrangements Using Rounded Arithmetic. 197-207
Electronic Edition (ACM DL) BibTeX
Keiko Imai, S. Sumino, Hiroshi Imai:
Minimax Geometric Fitting of Two Corresponding Sets of Points. 206-275
Electronic Edition (ACM DL) BibTeX
David Salesin, Jorge Stolfi, Leonidas J. Guibas:
Epsilon Geometry: Building Robust Algorithms from Imprecise Computations. 208-217
Electronic Edition (ACM DL) BibTeX
Erik Brisson:
Representing Geometric Structures in d Dimensions: Topology and Order. 218-227
Electronic Edition (ACM DL) BibTeX
Pascal Lienhardt:
Subdivisions of n-Dimensional Spaces and n-Dimensional Generalized Maps. 228-236
Electronic Edition (ACM DL) BibTeX
Jean-Daniel Boissonnat, Mariette Yvinec:
Probing a Scene of Non Convex Polyhedra. 237-246
Electronic Edition (ACM DL) BibTeX
Binay K. Bhattacharya, David G. Kirkpatrick, Godfried T. Toussaint:
Determining Sector Visibility of a Polygon. 247-253
Electronic Edition (ACM DL) BibTeX

John Hershberger, Subhash Suri:
Finding Tailored Partitions. 255-265
Electronic Edition (ACM DL) BibTeX
Jan-Ming Ho, D. T. Lee:
Bounded Diameter Minimum Spanning Trees and Related Problems. 276-282
Electronic Edition (ACM DL) BibTeX
Alok Aggarwal, Hiroshi Imai, Naoki Katoh, Subhash Suri:
Fining k Points with Minimum Spanning Trees and Related Problems. 283-291
Electronic Edition (ACM DL) BibTeX
Marshall W. Bern, Howard J. Karloff, Prabhakar Raghavan, Baruch Schieber:
Fast Geometric Approximation Techniques and Geometric Embedding Problems. 292-301
Electronic Edition (ACM DL) BibTeX
Odile Marcotte, Subhash Suri:
On Geometric Matching. 302-314
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal:
Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number. 315-325
Electronic Edition (ACM DL) BibTeX
Rex A. Dwyer:
Higher-Dimensional Voronoi Diagrams in Linear Expected Time. 326-333
Electronic Edition (ACM DL) BibTeX
Esther M. Arkin, Robert Connelly, Joseph S. B. Mitchell:
On Monotone Paths Among Obstacles with Applications to Planning Assemblies. 334-343
Electronic Edition (ACM DL) BibTeX

W. T. Liou, Jimmy J. M. Tan, Richard C. T. Lee:
Minimum Partitioning Simple Rectilinear Polygons in o(n log log n) Time. 344-353
Electronic Edition (ACM DL) BibTeX
Jack Snoeyink, John Hershberger:
Sweeping Arrangements of Curves. 354-363
Electronic Edition (ACM DL) BibTeX
Peter Egyed, Rephael Wenger:
Stabbing Pairwise Disjoint Translates in Linear Time. 364-369
Electronic Edition (ACM DL) BibTeX
Joseph O'Rourke, Catherine A. Schevon:
Computing the Geodesic Diameter of a 3-Polytope. 370-379
Electronic Edition (ACM DL) BibTeX
Jim Ruppert, Raimund Seidel:
On the Difficulty of Tetrahedralizing 3-Dimensional Non-Convex Polyhedra. 380-392
Electronic Edition (ACM DL) BibTeX
Bernard Chazelle, Leonidas Palios:
Triangulating a Non-Convex Polytype. 393-400
Electronic Edition (ACM DL) BibTeX