6. CCCG 1994: Saskatoon, Saskatchewan, Canada

Arrangements I

• Tetsuo Asano, Takeshi Tokuyama: Topological Walk Revisited. 1-6
• William L. Steiger, Ileana Streinu: A Pseudo-Algorithmic Separation of Lines from Pseudo-Lines. 7-11
• Mary Inaba, Yasukazu Aoki, Susumu Hasegawa: Level Difference of the Reconstructed Arrangement. 12-17

Visibility Graphs

• Anna Lubiw, Naji Mouawad: Interval Graphs as Visibility Graphs of Simple Polygons Part 1: Parachutes. 18-23
• Michel Pocchiola, Gert Vegter: Minimal Tangent Visibility Graphs. 24-29
• Shiou-Yi Lin, Chiuyuan Chen: Planar Visibility Graphs. 30-35
• Herbert Edelsbrunner: Modeling with Simplicial Complexes. 36-44

Motion Planning

• Vincenzo Ferrucci, Mark H. Overmars, Anil S. Rao, Jules Vleugels: Hunting Voronoi Vertices in Non-Polygonal Domains. 45-50
• Chantal Wentink, Otfried Schwarzkopf: Motion Planning for Vacuum Cleaner Robots. 51-56
• Siu-Wing Cheng: Widest Empty Corridor with Multiple Links and Right-angle Turns. 57-62

Nearest Neighbours

• Andreas Brinkman, Thorsten Graf, Klaus Hinrichs: The Colored Quadrant Priority Search Tree with an Application to the all-nearest-foreign-neighbors Problem. 63-68
• Thorsten Graf, Klaus Hinrichs: Distribution Algorithms for the all-nearest-foreign-neighbors Problem in Arbitrary L^t-metrics. 69-74
• Sergei Bespamyatnikh: The Region Approach for some Dynamic Closest-Point Problems. 75-80

Illumination

• Vladimir Estivill-Castro, Jorge Urrutia: Optimal Floodlight Illumination of Orthogonal Art Galleries. 81-86
• William L. Steiger, Ileana Streinu: Positive and Negative Results on the Floodlight Problem. 87-92

Arrangements II

• Chuzo Iwamoto, Godfried T. Toussaint: Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-complete. 93-98
• Hervé Brönnimann, Bernard Chazelle: Optimal Slope Selection Via Cuttings. 99-103

Paths in a Polygon

• John Hershberger, Jack Snoeyink: An Efficient Solution to the Zookeeper's Problem. 104-109
• Evanthia Papadopoulou, D. T. Lee: Shortest Paths in a Simple Polygon in the Presence of Forbidden Vertices. 110-115
• Peter Yamamoto: Computing the Dent Diameter of a Polygon. 116-121

Voronoi Diagrams

• Olivier Devillers, Mordecai J. Golin, Klara Kedem, Stefan Schirra: Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points. 122-127
• Martin Held: On Computing Voronoi Diagrams of Convex Polyhedra by Means of Wavefront Propagation. 128-133
• Abhi Dattasharma: Some Qualitative Properties of a Generalized Voronoi Diagram for Convex Polyhedra in d-dimensions. 134-139

Geometric Graphs

• Srinivasa Rao Arikati, Anil Maheshwari, Christos D. Zaroliagis: Saving Bits Made Easy. 140-146
• Timothy Law Snyder, J. Michael Steele: Worst-Case TSP Point Sets in All Dimensions are Asymptotically Equidistributed. 147-152

Convex Hulls

• Olivier Devillers, Mordecai J. Golin: Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas. 153-158
• Tsuyoshi Ono: An Eight-Way Perturbation Technique for the Three-Dimensional Convex Hull. 159-164

Delauny Triangulations I

• Jean-Michel Moreau: Hierarchical Delaunay Triangulation. 165-170
• Hiroshi Inagaki, Kokichi Sugihara: Numerically Robust Algorithm for Contructing Constrained Delaunay Triangulation. 171-176
• Andreas Voigtmann, Ludger Becker, Klaus Hinrichs: The Contrained Delaunay Pyramid - A Model for Reconstructing Surfaces at Multiple Resolutions. 177-182

Polygons

• Laxmi Gewali: Recognizing S-Star Polygons. 183-188
• Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink, Joseph S. B. Mitchell: Generating Random x-Monotone Polygons with Given Vertices. 189-194

Delauny Triangulations II

• Francisco Santos: On Delaunay oriented Matroids. 195-200
• Timothy Lambert: The Delaunay Triangulation Maximizes the Mean Inradius. 201-206

Optical Model

• Y. B. Karasik: Optical Computer Vision. 207-211
• Y. B. Karasik: Constructing Optically in Constant Time the K-Level of an Arrangement of Lines in the Plane and Other Related Problems. 212-218

Applications

• Christopher M. Gold: Persistent Spatial Relations - a Systems Design Objective. 219-224
• Karen L. Daniels, Victor Milenkovic: Limited Gaps. 225-230
• Paul G. Mezey: The T-Hull Approach to Shape Analysis. 231-236

Implementation

• Peter Hertling, Klaus Weihrauch: Levels of Degeneracy and Exact Lower Complexity Bounds for Geometric Algorithms. 237-242
• David P. Dobkin, Ayellet Tal: GASP - An Animation System for Computational Geometry. 243-249
• Manuel Abellanas, Ferran Hurtado, Pedro A. Ramos: Tolerance of Geometric Structures. 250-255

Intersection

• Binhai Zhu: Intersection Detection and Computation of Manhattan Terrains. 256-262
• Timothy M. Chan: A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections. 263-268
• Paul Colley, Henk Meijer, David Rappaport: Optimal Nearly-Similar Polygon Stabbers of Convex Polygons. 269-274

Graphs

• Ryan Hayward, Paul E. Kearney: Tolerance-Free NeST Representations. 275-280
• Giuseppe Liotta, Francesco Vargiu, Giuseppe Di Battista: Orthogonal Drawings with the Minimum Number of Bends. 281-286
• Michael B. Dillencourt, Warren D. Smith: Graph-Theoretical Conditions for Inscribability and Delaunay Realizability. 287-292

Guard Problems I

• Hazel Everett, Eduardo Rivera-Campo: Edge Guarding a Triangulated Polyhedral Terrain. 293-295
• Siu-Ming Yiu, A. Choi: Edge Guards on a Fortress. 296-301
• Ervin Györi, Frank Hoffmann, Klaus Kriegel, Thomas C. Shermer: Generalized Guarding and Partitioning for Rectilinear Polygons. 302-307

Optimization

• Joseph L. Ganley, James P. Cohoon: Optimal Rectilinear Steiner Minimal Trees in O (n²2.62ⁿ) Time. 308-313
• Claudio Mirolo: Convex Minimization on a Grid and Applications. 314-319
• Leonidas Palios: On the Number of Extrema of a Polyhedron. 320-325

Triangulations

• Scott A. Mitchell: Cardinality Bounds for Triangulations with Bounded Minimum Angle. 326-331
• Cao An Wang: An Optimal Algorithm for Greedy Triangulation of a Set of Points. 332-338
• Tamal K. Dey, Michael B. Dillencourt, Subir Kumar Ghosh: Triangulating with High Connectivity. 339-343

Polyhedra

• Prosenjit Bose, David Bremner, Godfried T. Toussaint: All Convex Polyhedra can be Clamped with Parallel Jaw Grippers. 344-349
• Leonidas Palios: Optimal Tetrahedralization of the 3d-Region between a Convex Polyhedron and a Convex Polygon. 350-356
• Abhi Dattasharma: The Size of a Generalized Voronoi Diagram for Convex Polyhedra in d-dimensions. 357-362

Visibility

• David Bremner: Link-2-Convex One-Fillable Polygons are Starshaped. 363-368
• Stephen K. Wismath: Reconstruction of Parallel Line Segments From Endpoint Visibility Information. 369-374
• Danny Z. Chen: Determining Weak External Visibility of Polygons in Parallel. 375-380

Guard Problems II

• Patrice Belleville, Prosenjit Bose, Jurek Czyzowicz, Jorge Urrutia, Joseph Zaks: K-Guarding Polygons on the Plane. 381-386
• Gregorio Hernández-Peñalver: Controlling Guards. 387-392
• Manuel Abellanas, Jesus Garcia-Lopez, Ferran Hurtado: Consecutive Guards. 393-398