yao.pa@XEROX.COM (02/09/90)
Here is the preliminary version of the technical program. --------------------------- The Sixth Annual Symposium on Computational Geometry June 6-8, 1990 Clark Kerr Campus University of California Berkeley, California Wednesday Morning, June 6 Session 1: 8:40-10:00 am Chair: Frances Yao, Xerox PARC 8:40 Cutting Hyperplane Arrangements Jiri Matousek, Charles University, Czechoslovakia 9:00 Some New Bounds for Epsilon-NetsJanos Pach, New York University and Hungarian Academy of Sciences, Gerhard Woeginger, Technische Universitat Graz 9:20 How to Net a Lot with Little: Small Epsilon-nets for Disks and Halfspaces Jiri Matousek, Charles University, Raimund Seidel, UC Berkeley, Emo Welzl, Freie Universitat Berlin 9:40 Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems Bernard Chazelle, Princeton University, Micha Sharir, New York University and Tel Aviv University Coffee Break 10:00-10:20 am Session 2: 10:20 am-12:00 pm Chair: Mikhail Atallah, Purdue University 10:20 O (n log log n) Polygon Triangulation With Simple Data Structures David G. Kirkpatrick and Maria M. Klawe, University of British Columbia, Robert E. Tarjan, Princeton University 10:40 A Polynomial Time Algorithm for the MinMax Angle Triangulation Herbert Edelsbrunner and Tiow Seng Tan, University of Illinois 11:00 Structured Visibility Profiles with Applications to Problems in Simple Polygons Paul J. Heffernan and Joseph S. B. Mitchell, Cornell University 11:20 Computing the Minimum Link Path Among a Set of Obstacles in the Plane Joseph S. B. Mitchell, Cornell University, Gunter Rote and Gerhard Woeginger, Technische Universitat Graz 11:40 Parallel Methods for Visibility and Shortest Path Problems in Simple Polygons Michael T. Goodrich, The Johns Hopkins University, Steven B. Shauck, Westinghouse Electric Corporation, Sumanta Guha, University of Michigan Lunch Break 12:00-1:30 pm Wednesday Afternoon, June 6 Session 3: Invited Lecture 1:30 Differential Geometry and Computation S. S. Chern, University of California, Berkeley Session 4: 2:30-3:30 pm Chair: Ronald Graham, AT&T Bell Laboratories 2:30 On the Combinatorial Complexity of Hyperplane Transversals Sylvain E. Cappell, New York University, Jacob E.Goodman, The City University of New York, Janos Pach, New York University and Hungarian Academy of Sciences, Richard Pollack, New York University, Micha Sharir, New York University and Tel Aviv University, Rephael Wenger, DIMACS Center 2:50 On the Limited Abilities of Ray-Oracles Peter Gritzmann, University of Augsburg and University of Washington, Victor Klee and John Westwater, University of Washington 3:10 Computational Complexity of Combinatorial Surfaces Gert Vegter, University of Groningen, The Netherlands, Chee K. Yap, New York University Coffee Break 3:30-3:50 pm Session 5: 3:50-5:10 pm Chair: Tetsuo Asano, Osaka Electro-Communication University 3:50 Points and Triangles in the Plane and Halving Planes in Space Bernard Chazelle, Princeton University, Herbert Edelsbrunner, Univeristy of Illinois, Leonidas J. Guibas, DEC SRC and Stanford University, Micha Sharir, New York University and Tel Aviv University 4:10 Selecting Multiply Covered Points and Reducing the Size of Delaunay Triangulations Bernard Chazelle, Princeton University, Herbert Edelsbrunner, University of Illinois, Leonidas J. Guibas, DEC SRC and Stanford University, John E. Hershberger, DEC SRC, Raimund Seidel, UC Berkeley, Micha Sharir, New York University and Tel Aviv University 4:30 Tiling the Plane with One Tile Daniele Beauquier and Maurice Nivat, LITP Universite Paris VI et VII 4:50 A Trivial Knot Whose Spanning Disks Have Exponential Size Jack Snoeyink, Stanford University Thursday Morning, June 7 Session 6: Invited Lecture 9:00 The Demands on Computational Geometry Made by Image Rendering James F. Blinn, California Institute of Technology Session 7: 10:00 am-12:00 pm Chair: David Dobkin, Princeton University 10:00 Geometric Computations with Algebraic Varieties of Bounded Degree Chanderjit Bajaj, Purdue University 10:20 On Computing the Intersection of B-Splines B. K. Natarajan, Carnegie Mellon University and Hewlett-Packard Laboratories Coffee Break 10:40--11:00 am 11:00 Merging Visibility Maps Mark H. Overmars, Utrecht University, Micha Sharir, New York University and Tel Aviv University 11:20 Stabbing and Ray Shooting in 3 Dimensional Space Marco Pellegrini, New York University 11:40 K-d Trees for Semidynamic Point Sets Jon Bentley, AT&T Bell Laboratories Lunch Break 12:00-1:30 pm Thursday Afternoon, June 7 Session 8: 1:30-3:10 pm Chair: Pravin Vaidya, University of Illinois 1:30 On the Optimal Bisection of a Polygon Elias Koutsoupias and Christos H. Papadimitriou, UC San Diego, Martha Sideri, Computer Technology Institute, Greece 1:50 Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs Pankaj Agarwal, DIMACS Center and Duke University, Herbert Edelsbrunner, University of Illinois, Otfried Schwarzkopf and Emo Welzl, Freie Universitat Berlin 2:10 Linear Programming and Convex Hulls Made Easy Raimund Seidel, University of California, Berkeley 2:30 On Simultaneous Inner and Outer Approximation of Shapes Rudolf Fleischer and Kurt Mehlhorn, Universitat des Saarlandes, Gunter Rote, Technische Universitat Graz, Emo Welzl, Freie Universitat Berlin, Chee Yap, New York University 2:50 Maximin Location of Convex Objects in a Polygon and Related Dynamic Voronoi Diagrams Hiromi Aonuma and Hiroshi Imai, Kyushu University, Keiko Imai, Kyushu Institute of Technology, Takeshi Tokuyama, IBM Tokyo Research Laboratory Coffee Break 3:10-3:30 pm Session 9: 3:30-4:50 pm Chair: Steve Fortune, AT&T Bell Laboratories 3:30 Constructing Strongly Convex Hulls Using Exact or Rounded Arithmetic Victor Milenkovic and Zhenyu Li, Harvard University 3:50 Finding Compact Coordinate Representations for Polygons and Polyhedra Victor Milenkovic, Harvard University, Lee R. Nackman, IBM Thomas J. Watson Research Center 4:10 Some Provably Hard Crossing Number Problems Daniel Bienstock, Columbia University 4:30 Enumeration and Visibility Problems in Integer Lattices Evangelos Kranakis, Centre for Mathematics and Computer Science, The Netherlands, Michel Pocchiola, Ecole Normale Superieure, France Friday Morning, June 8 Session 10: Invited Lecture 9:00 Implementing Projective Geometry via Symbolic Computation Dana S. Scott, Carnegie Mellon University Session 11: 10:00 am-12:00 pm Chair: Mikhail Atallah, Purdue University 10:00 An Exact Algorithm for Kinodynamic Planning in the Plane John Canny and Ashutosh Rege, University of California, Berkeley, John Reif, Duke University 10:20 Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures Helmut Alt, Freie Universitat Berlin, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Naher, Stefan Schirra and Christian Uhrig, Universitat des Saarlandes Coffee Break 10:40 am-11:00 am 11:00 Provably Good Approximation Algorithms for Optimal Kinodynamic Planning for Cartesian Robots and Open Chain Manipulators Bruce Donald and Patrick Xavier, Cornell University 11:20 Shortest Rectilinear Paths Among Weighted Obstacles C. D. Yang, T. H. Chen and D.T. Lee, Northwestern University 11:40 On Minimal Rectilinear Steiner Trees in All Dimensions Timothy L. Snyder, Georgetown University Lunch Break 12:00-1:30 pm Friday Afternoon, June 8 Session 12: 1:30-3:10 pm Chair: Marshall Bern, Xerox PARC 1:30 Selecting Distances in the Plane Pankaj K. Agarwal, DIMACS Center and Duke University, Boris Aronov, DIMACS Center, Micha Sharir, New York University and Tel Aviv University, Subhash Suri, Bellcore 1:50 Reconstructing Sets from Interpoint Distances Steven Skiena, SUNY at Stony Brook, Warren D. Smith, AT&T Bell Laboratories, Paul Lemke, Rensselaer Polytechnic Institute 2:10 Computing the Minimum Hausdorff Distance for Point Sets Under Translation Dan P. Huttenlocher, Cornell University, Klara Kedem, Tel Aviv University 2:30 On Solving Geometric Optimization Problems Using Shortest Paths Elefterios A. Melissaratos and Diane L. Souvaine, Rutgers University 2:50 Shortest Paths on a Polyhedron Jindong Chen and Yijie Han, University of Kentucky