6. Symposium on Computational Geometry 1990: Berkeley, CA, USA

Session 1

• Jirí Matousek:
  Cutting Hyperplane Arrangements. 1-9
  
• János Pach, Gerhard J. Woeginger:
  Some New Bounds for Epsilon-Nets. 10-15
  
• Jirí Matousek:
  Raimund Seidel, Emo Welzl: How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces. 16-22
  
• Bernard Chazelle, Micha Sharir, Emo Welzl:
  Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems. 23-33
  

Session 2

• David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
  Polygon Triangulation in O(n log log n) Time with Simple Data-Structures. 34-43
  
• Herbert Edelsbrunner, Tiow Seng Tan, Roman Waupotitsch:
  An O(n²log n) Time Algorithm for the MinMax Angle Triangulation. 44-52
  
• Paul J. Heffernan, Joseph S. B. Mitchell:
  Structured Visibility Profiles with Applications to Problems in Simple Polygons (Extended Abstract). 53-62
  
• Joseph S. B. Mitchell, Günter Rote, Gerhard J. Woeginger:
  Minimum-Link Paths Among Obstacles in the Plane. 63-72
  
• Michael T. Goodrich, Steven B. Shauck, Sumanta Guha:
  Parallel Methods for Visibility and Shortest Path Problems in Simple Polygons (Preliminary Version). 73-82
  

Session 3

• Sylvain E. Cappell, Jacob E. Goodman, János Pach, Richard Pollack, Micha Sharir, Rephael Wenger:
  The Combinatorial Complexity of Hyperplane Transversals. 83-91
  
• Peter Gritzmann, Victor Klee, John Westwater:
  On the Limited Power of Linear Probes and Other Optimization Oracles. 92-101
  
• Gert Vegter, Chee-Keng Yap:
  Computational Complexity of Combinatorial Surfaces. 102-111
  

Session 4

• Boris Aronov, Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Rephael Wenger:
  Points and Triangles in the Plane and Halving Planes in Space. 112-115
  
• Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir:
  Slimming Down by Adding: Selecting Heavily Covered Points. 116-127
  
• Danièle Beauquier, Maurice Nivat:
  Tiling the Plane with One Tile. 128-138
  
• Jack Snoeyink:
  A Trivial Knot Whose Spanning Disks Have Exponential Size. 139-147
  

Session 5

• Chandrajit L. Bajaj:
  Geometric Computations with Algebraic Varieties of Bounded Degree. 148-156
  
• B. K. Natarajan:
  On Computing the Intersection of B-Splines (Extended Abstract). 157-167
  
• Mark H. Overmars, Micha Sharir:
  Merging Visibility Maps. 168-176
  
• Marco Pellegrini:
  Stabbing and Ray Shooting in 3 Dimensional Space. 177-186
  
• Jon Louis Bentley:
  K-d Trees for Semidynamic Point Sets. 187-197
  

Session 6

• Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri:
  On the Optimal Bisection of a Polygon (Extended Abstract). 198-202
  
• Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, Emo Welzl:
  Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs. 203-210
  
• Raimund Seidel:
  Linear Programming and Convex Hulls Made Easy. 211-215
  
• Rudolf Fleischer, Kurt Mehlhorn, Günter Rote, Emo Welzl, Chee-Keng Yap:
  On Simultaneous Inner and Outer Approximation of Shapes. 216-224
  
• Hiromi Aonuma, Hiroshi Imai, Keiko Imai, Takeshi Tokuyama:
  Maximin Location of Convex Objects in a Polygon and Related Dynamic Voronoi Diagrams. 225-234
  

Session 7

• Zhenyu Li, Victor Milenkovic:
  Constructing Strongly Convex Hulls Using Exact or Rounded Arithmetic. 235-243
  
• Victor Milenkovic, Lee R. Nackman:
  Finding Compact Coordinate Representations for Polygons and Polyhedra. 244-252
  
• Daniel Bienstock:
  Some Provably Hard Crossing Number Problems. 253-260
  
• Evangelos Kranakis, Michel Pocchiola:
  Enumeration and Visibility Problems in Integer Lattices (Extended Abstract). 261-270
  

Session 8

• John F. Canny, Ashutosh Rege, John H. Reif:
  An Exact Algorithm for Kinodynamic Planning in the Plane. 271-280
  
• Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Näher, Stefan Schirra, Christian Uhrig:
  Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures. 281-289
  
• Bruce Randall Donald, Patrick G. Xavier:
  Provably Good Approximation Algorithms for Optimal Kinodynamic Planning for Cartesian Robots and Open Chain Manipulators. 290-300
  
• D. T. Lee, T. H. Chen, Chung-Do Yang:
  Shortest Rectilinear Paths among Weighted Obstacles. 301-310
  
• Timothy Law Snyder:
  On Minimal Rectilinear Steiner Trees in All Dimensions. 311-320
  

Session 9

• Pankaj K. Agarwal, Boris Aronov, Micha Sharir, Subhash Suri:
  Selecting Distances in the Plane. 321-331
  
• Steven Skiena, Warren D. Smith, Paul Lemke:
  Reconstructing Sets from Interpoint Distances (Extended Abstract). 332-339
  
• Daniel P. Huttenlocher, Klara Kedem:
  Computing the Minimum Hausdorff Distance for Point Sets Under Translation. 340-349
  
• Elefterios A. Melissaratos, Diane L. Souvaine:
  On Solving Geometric Optimization Problems Using Shortest Paths. 350-359
  
• Jindong Chen, Yijie Han:
  Shortest Paths on a Polyhedron. 360-369
  
• A. Knight, J. May, Jeff McAffer, T. Nguyen, Jörg-Rüdiger Sack:
  A Computational geometry Workbench. 370