12. Symposium on Computational Geometry 1996: Philadelphia, PA, USA

Proceedings of the Twelfth Annual Symposium on Computational Geometry, May 24-26, 1996, Philadelphia, PA, USA. ACM Press, 1996, ISBN 0-89791-832-0

Regular Papers

Jeff Erickson:
New Lower Bounds for Convex Hull Problems in Odd Dimensions. 1-9
Electronic Edition (ACM DL) BibTeX
Nina Amenta, Günter M. Ziegler:
Shadows and Slices of Polytopes. 10-19
Electronic Edition (ACM DL) BibTeX
Otfried Schwarzkopf, Micha Sharir:
Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and Its Applications. 20-29
Electronic Edition (ACM DL) BibTeX
Stefan Felsner:
On the Number of Arrangements of Pseudolines. 30-37
Electronic Edition (ACM DL) BibTeX
Gill Barequet, Matthew Dickerson, David Eppstein:
On Triangulating Three-Dimensional Polygons. 38-47
Electronic Edition (ACM DL) BibTeX
Scott A. Mitchell, Stephen A. Vavasis:
An Aspect Ratio Bound for Triangulating a d-Grid Cut by a Hyperplane (Extended Abstract). 48-57
Electronic Edition (ACM DL) BibTeX
David Eppstein:
Linear Complexity Hexahedral Mesh Generation. 58-67
Electronic Edition (ACM DL) BibTeX
Sandy Irani, Prabhakar Raghavan:
Combinatorial and Experimental Results for Randomized Point Matching Algorithms. 68-77
Electronic Edition (ACM DL) BibTeX
Satyan R. Coorg, Seth J. Teller:
Temporally Coherent Conservative Visibility (Extended Abstract). 78-87
Electronic Edition (ACM DL) BibTeX
Chandrajit L. Bajaj, Valerio Pascucci:
Splitting a Complex of Convex Polytopes In Any Dimension. 88-97
Electronic Edition (ACM DL) BibTeX
Robert J. Lang:
A Computational Algorithm for Origami Design. 98-105
Electronic Edition (ACM DL) BibTeX
Micha Sharir:
A Near-Linear Algorithm for the Planar 2-Center Problem. 106-112
Electronic Edition (ACM DL) BibTeX
Matthew J. Katz, Frank Nielsen:
On Piercing Sets of Objects. 113-121
Electronic Edition (ACM DL) BibTeX
Micha Sharir, Emo Welzl:
Rectilinear and Polygonal p-Piercing and p-Center Problems. 122-132
Electronic Edition (ACM DL) BibTeX
Wei Chen, Koichi Wada, Kimio Kawaguchi:
Parallel Robust Algorithms for Constructing Strongly Convex Hulls. 133-140
Electronic Edition (ACM DL) BibTeX
Jonathan Richard Shewchuk:
Robust Adaptive Floating-Point Geometric Predicates. 141-150
Electronic Edition (ACM DL) BibTeX
Simon Kahan, Jack Snoeyink:
On the Bit Complexity of Minimum Link Paths: Superquadratic Algorithms for Problems Solvable in Linear Time. 151-158
Electronic Edition (ACM DL) BibTeX
Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel, Raimund Seidel, Christian Uhrig:
Checking Geometric Programs or Verification of Geometric Structures. 159-165
Electronic Edition (ACM DL) BibTeX
Nancy M. Amato, Edgar A. Ramos:
On Computing Voronoi Diagrams by Divide-Prune-and-Conquer. 166-175
Electronic Edition (ACM DL) BibTeX
Neelima Gupta, Sandeep Sen:
Faster Output-Sensitive Parallel Convex Hulls for d<=3: Optimal Sublogarithmic Algorithms for Small Outputs. 176-185
Electronic Edition (ACM DL) BibTeX
Guy E. Blelloch, Gary L. Miller, Dafna Talmor:
Developing a Practical Projection-Based Parallel Delaunay Algorithm. 186-195
Electronic Edition (ACM DL) BibTeX
Siu-Wing Cheng, Yin-Feng Xu:
Approaching the Largest beta-Skeleton within a Minimum Weight Triangulation. 196-203
Electronic Edition (ACM DL) BibTeX
Matthew Dickerson, Mark H. Montague:
A (Usually?) Connected Subgraph of the Minimum Weight Triangulation. 204-213
Electronic Edition (ACM DL) BibTeX
Ferran Hurtado, Marc Noy, Jorge Urrutia:
Flipping Edges in Triangulations. 214-223
Electronic Edition (ACM DL) BibTeX
Tomonari Masada, Hiroshi Imai, Keiko Imai:
Enumeration of Regular Triangulations. 224-233
Electronic Edition (ACM DL) BibTeX
G. D. Ramkumar:
An Algorithm to Compute the Minkowski Sum Outer-face of Two Simple Polygons. 234-241
Electronic Edition (ACM DL) BibTeX
Jean-Daniel Boissonnat, Sylvain Lazard:
A Polynomial-Time Algorithm for Computing a Shortest Path of Bounded Curvature Amidst Moderate Obstacles (Extended Abstract). 242-251
Electronic Edition (ACM DL) BibTeX
Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
d₁-Optimal Motion for a Rod (Extended Abstract). 252-263
Electronic Edition (ACM DL) BibTeX
Kathleen Romanik, Sven Schuierer:
Optimal Robot Localization in Trees. 264-273
Electronic Edition (ACM DL) BibTeX
Ernst P. Mücke, Isaac Saias, Binhai Zhu:
Fast Randomized Point Location Without Preprocessing in Two- and Three-dimensional Delaunay Triangulations. 274-283
Electronic Edition (ACM DL) BibTeX
Timothy M. Chan:
Fixed-Dimensional Linear Programming Queries Made Easy. 284-290
Electronic Edition (ACM DL) BibTeX
Michel Pocchiola, Gert Vegter:
Pseudo-Triangulations: Theory and Applications. 291-300
Electronic Edition (ACM DL) BibTeX
Alon Efrat, Alon Itai:
Improvements on Bottleneck Matching and Related Problems Using Geometry. 301-310
Electronic Edition (ACM DL) BibTeX
Kasturi R. Varadarajan:
Approximating Monotone Polygonal Curves Using the Uniform Metric. 311-318
Electronic Edition (ACM DL) BibTeX
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia:
Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version). 319-328
Electronic Edition (ACM DL) BibTeX
Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan:
Approximating Shortest Paths on a Convex Polytope in Three Dimensions. 329-338
Electronic Edition (ACM DL) BibTeX
Joonsoo Choi, Chee-Keng Yap:
Monotonicity of Rectilinear Geodesics in d-Space (Extended Abstract). 339-348
Electronic Edition (ACM DL) BibTeX
Daniel A. Spielman, Shang-Hua Teng:
Disk Packings and Planar Separators. 349-358
Electronic Edition (ACM DL) BibTeX
Gyula Károlyi, János Pach, Géza Tóth:
Ramsey-Type Results for Geometric Graphs. 359-365
Electronic Edition (ACM DL) BibTeX

Communications

Mary Inaba, Hiroshi Imai, Naoki Katoh:
Experimental Results of Randomized Clustering Algorithm. C-1-C-2
Electronic Edition (ACM DL) BibTeX
James E. Baker, Isabel F. Cruz, Giuseppe Liotta, Roberto Tamassia:
Animating Geometric Algorithms Over the Web. C-3-C-4
Electronic Edition (ACM DL) BibTeX
Mark de Berg, René van Oostrum, Mark H. Overmars:
Simple Traversal of a Subdivision Without Extra Storage. C-5-C-6
Electronic Edition (ACM DL) BibTeX
Ferran Hurtado, Marc Noy:
The Graph of Triangulations of a Convex Polygon. C-7-C-8
Electronic Edition (ACM DL) BibTeX
Gill Barequet, Micha Sharir:
Partial Surface Matching by Using Directed Footprints. C-9-C-10
Electronic Edition (ACM DL) BibTeX
David Avis, Prosenjit Bose, Godfried T. Toussaint, Thomas C. Shermer, Binhai Zhu, Jack Snoeyink:
On the Sectional Area of Convex Polytopes. C-11-C-12
Electronic Edition (ACM DL) BibTeX
Elmar Schömer, Jürgen Sellen, Marek Teichmann, Chee-Keng Yap:
Smallest Enclosing Cylinders. C-13-C-14
Electronic Edition (ACM DL) BibTeX
Klara Kedem, Yana Yarmovski:
Curve Based Stereo Matching Using the Minimum Hausdorff Distance. C-15-C-18
Electronic Edition (ACM DL) BibTeX
Chandrasekhar Pisupati, Lawrence B. Wolff, Wayne Mitzner, Elias A. Zerhouni:
Geometric Tree Matching with Applications to 3D Lung Structures. C-19-C-20
Electronic Edition (ACM DL) BibTeX

Videos

Nina Amenta:
Four-Polytopes and a Funeral (for my conjecture). V-1-V-2
Electronic Edition (ACM DL) BibTeX
Sherif Ghali, A. James Stewart:
Maintenance of the Set of Segments Visible from a Moving Viewpoint in Two Dimensions. V-3-V-4
Electronic Edition (ACM DL) BibTeX
Brian Mirtich, John F. Canny:
Testing Control Systems Through Dynamic Simulation. V-5-V-6
Electronic Edition (ACM DL) BibTeX
Patrice Belleville, J. Mark Keil, Michael McAllister, Jack Snoeyink:
On Computing Edges That Are In All Minimum-Weight Triangulations. V-7-V-8
Electronic Edition (ACM DL) BibTeX
Matthew Dickerson, Daniel Scharstein:
The Rotation Diagram and Optimal Containing Placements of a Convex Polygon. V-9-V-10
Electronic Edition (ACM DL) BibTeX
Frédo Durand, Rachel Orti, Stéphane Rivière, Claude Puech:
Radiosity in Flatland Made Visibly Simple: Using the Visibility Complex for Lighting Simulation of Dynamic Scenes in Flatland. V-11-V-12
Electronic Edition (ACM DL) BibTeX
Martin Held, James T. Klosowski, Joseph S. B. Mitchell:
Collision Detection for Fly-Throughs in Virtual Environments. V-13-V-14
Electronic Edition (ACM DL) BibTeX
Subodh Kumar, Dinesh Manocha:
The Power of Coherence: Fast Tessellation of Surfaces. V-15-V-16
Electronic Edition (ACM DL) BibTeX
Tsuyoshi Ono, Yoshiaki Kyoda, Tomonari Masada, Kazuyoshi Hayase, Tetsuo Shibuya, Motoki Nakade, Mary Inaba, Hiroshi Imai, Keiko Imai, David Avis:
A Package for Triangulations. V-17-V-18
Electronic Edition (ACM DL) BibTeX