The 12th Annual ACM Symposium on Computational Geometry Sessions: Continental breakfast: 7:15am-8:00am Plenary Session: 8:00am-9:00am Session S1: Contributed Talks Friday, May 24, 1996 9:15am-10:55am Session chair: Sue Whitesides (McGill University) 9:15am New Lower Bounds for Convex Hull Problems in Odd Dimensions Jeff Erickson 9:40am Shadows and Slices of Polytopes Nina Amenta, G\"unter Ziegler 10:05am Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and its Applications Otfried Schwarzkopf, Micha Sharir 10:30am On the Number of Arrangements of Pseudolines Stefan Felsner Break: 10:55am-11:20am Session S2: Contributed Talks Friday, May 24, 1996 11:20am-12:35pm Session chair: Marshall Bern (Xerox PARC) 11:20am On Triangulating Three-Dimensional Polygons Gill Barequet, Matthew Dickerson, David Eppstein 11:45am An Aspect Ratio Bound for Triangulating a $d$-Grid Cut by a Hyperplace Scott A. Mitchell, Stephen A. Vavasis 12:10pm Linear Complexity Hexahedral Mesh Generation David Eppstein Lunch: 12:35pm-2:00pm Session S3: Contributed Talks Friday, May 24, 1996 2:00pm-3:40pm Session chair: Nicholas Patrikalakis (MIT) 2:00pm Combinatorial and Experimental Results for Randomized Point Matching Algorithms Sandy Irani, Prabhakar Raghavan 2:25pm Temporally Coherent Conservative Visibility Satyan Coorg, Seth Teller 2:50pm Splitting a Complex of Convex Polytopes in any Dimension Chandrajit L. Bajaj, Valerio Pascucci 3:15pm A Computational Algorithm for Origami Design Robert J. Lang Break: 3:40pm-4:05pm Session S4: Contributed Talks Friday, May 24, 1996 4:05pm-5:20pm Session chair: Pankaj K. Agarwal (Duke University) 4:05pm A Near-Linear Algorithm for the Planar 2-Center Problem Micha Sharir 4:30pm On Piercing Sets of Objects Matthew J. Katz, Franck Nielsen 4:55pm Rectilinear and Polygonal $p$-Piercing and $p$-Center Problems Micha Sharir, Emo Welzl Session S5: Business Meeting Friday, May 24, 1996 5:20pm- Session chair: Joseph Mitchell (SUNY-Stony Brook) Refreshments and business meeting. Continental breakfast: 7:15am-8:00am Plenary Session: 8:00am-9:00am Session S6: Contributed Talks Saturday, May 25, 1996 9:15am-10:55am Session chair: Victor Milenkovic (University of Miami) 9:15am Parallel Robust Algorithms for Constructing Strongly Convex Hulls Wei Chen, Koichi Wada, Kimio Kawaguchi 9:40am Robust Adaptive Floating-Point Geometric Predicates Jonathan Shewchuk 10:05am On the Bit Complexity of Minimum Link Paths: Superquadratic Algorithms for Problems Solvable in Linear time Simon Kahan, Jack Snoeyink 10:30am Checking Geometric Programs or Verification of Geometric Structures Kurt Mehlhorn, Stefan N\"aher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, Christian Uhrig Break: 10:55am-11:20am Session S7: Contributed Talks Saturday, May 25, 1996 11:20am-12:35pm Session chair: Pankaj K. Agarwal (Duke University) 11:20am On Computing Voronoi Diagrams by Divide-Prune-and-Conquer Nancy M. Amato, Edgar A. Ramos 11:45am Faster Output-Sensitive Parallel Convex Hulls for $d \le 3$: Optimal Sublogarithmic Algorithms for Small Outputs Neelima Gupta, Sandeep Sen 12:10pm Developing a Practical Projection-Based Parallel Delaunay Algorithm Guy Blelloch, Gary L. Miller, Dafna Talmor Lunch: 12:35pm-2:00pm Session S8: Contributed Talks Saturday, May 25, 1996 2:00pm-3:40pm Session chair: Joseph O'Rourke (Smith College) 2:00pm Approaching the Largest $\beta$-Skeleton within a Minimum Weight Triangulation Siu-Wing Cheng, Yin-Feng Xu 2:25pm The Exact Minimum Weight Triangulation Matthew T. Dickerson, Mark H. Montague 2:50pm Flipping Edges on Triangulations F. Hurtado, M. Noy, J. Urrutia 3:15pm Enumeration of Regular Triangulations Tomonari Masada, Hiroshi Imai, Keiko Imai Break: 3:40pm-4:05pm Session S9: Poster Session (Short Communications) Saturday, May 25, 1996 4:05pm-6:00pm Experimental Results of a Randomized Clustering Algorithm Mary Inaba, Hiroshi Imai, Naoki Katoh Animating Geometric Algorithms over the Web James E. Baker, Isabel F. Cruz, Giuseppe Liotta, Roberto Tamassia Simple Traversal of a Subdivision Without Extra Storage Mark de Berg, Marc van Kreveld, Ren\'e van Oostrum, Mark Overmars The Graph of Triangulations of a Convex Polygon F. Hurtado, M. Noy Partial Surface Matching by Using Directed Footprints Gill Barequet, Micha Sharir On the Sectional Area of Convex Polytopes D. Avis, P. Bose, T. Shermer, J. Snoeyink, G. Toussaint, B. Zhu Smallest Enclosing Cylinders Elmar Schomer, Jurgen Sellen, Marek Teichmann, Chee Yap Curve Based Stereo Matching Using the Minimum Hausdoff Distance Klara Kedem, Yana Yarmovski Approximate Geometric Matching of 3d Bronchial Tree Structures Chandrasekhar Pisupati, Lawrence Wolff, Wayne Mitzner, Elias Zerhouni Excursion: 6:00pm-10:00pm Continental breakfast: 7:15am-8:00am Plenary Session: 8:00am-9:00am Session S10: Contributed Talks Sunday, May 26, 1996 9:15am-10:55am Session chair: Olivier Devillers (INRIA, Sophia-Antipolis) 9:15am Algorithms to Compute the Convolution and Minkowski Sum Outer-Face of Two Simple Polygons G. D. Ramkumar 9:40am A Polynomial-time Algorithm for Computing a Shortest Path of Bounded Curvature Amidst Moderate Obstacles Jean-Daniel Boissonnat, Sylvain Lazard 10:05am $d_1$-Optimal Motion for a Rod Tetsuo Asano, David Kirkpatrick, Chee K. Yap 10:30am Optimal Robot Localization in Trees Kathleen Romanik, Sven Schuierer Break: 10:55am-11:20am Session S11: Contributed Talks Sunday, May 26, 1996 11:20am-12:35pm Session chair: Marc van Kreveld (Utrecht University) 11:20am Fast Randomized Point Location Without Preprocessing in Two-and Three-Dimensional Delaunay Triangulations Ernst P. M\"ucke, Isaac Saias, Binhai Zhu 11:45am Fixed-Dimensional Linear Programming Queries Made Easy Timothy M. Chan 12:10am Pseudo-Triangulations: Theory and Applications Michel Pocchiola, Gert Vegter Lunch: 12:35pm-2:00pm Session S12: Contributed Talks Sunday, May 26, 1996 2:00pm-3:40pm Session chair: Subhash Suri (Washington University) 2:00pm Improvements on Bottleneck Matching and Related Problems Using Geometry Alon Efrat, Alon Itai 2:25pm Approximating Monotone Polygonal Curves Using the Uniform Metric Kasturi R. Varadarajan 2:50pm Convex Drawings of Graphs in Two and Three Dimensions Marek Chrobak, Michael T. Goodrich, Roberto Tamassia 3:15pm Approximate Shortest Paths on a Convex Polytope in 3-d Kasturi R. Varadarajan Break: 3:40pm-4:05pm Session S13: Contributed Talks Sunday, May 26, 1996 4:05pm-5:20pm Session chair: Imre Barany (Hungarian Academy) 4:05pm Monotonicity of Rectilinear Geodesics in $d$-Space Joonsoo Choi, Chee-Keng Yap 4:30pm Disk Packings and Planar Separators Daniel A. Spielman, Shang-Hua Teng 4:55pm Ramsey-Type Results for Geometric Graphs Gyula Karolyi, Janos Pach, Geza Toth End of conference.