12. CCCG 2000: Fredericton, New Brunswick, Canada

Session C1: Polygons

• Erik D. Demaine, Martin L. Demaine, Craig S. Kaplan:
  Polygons Cuttable by a Circular Saw.
  
• Gill Barequet, Matthew Dickerson:
  The Translation-Scale Diagram for Point-Containing Placements of a Convex Polygon.
  
• Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin:
  Flipping your Lid.
  
• Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark H. Overmars, Michael A. Soss, Godfried T. Toussaint:
  Reconfiguring Convex Polygons.
  

Session I1: Invited Lecture

• Naoki Kato:
  Applications of Computational Geometry in Architecture.
  

Session C2.1: Circular Arcs

• Vladimir Filkov:
  Covering Points on a Circle with Circular Arcs.
  
• Stefan Langerman:
  On the Shooter Location Problem.
  
• Ralph P. Boland, Jorge Urrutia:
  Circular Ray Shooting: Slower but Surer.
  

Session C2.2: Visibility

• David G. Kirkpatrick:
  Guarding Alcove-Free Galleries .
  
• Jurek Czyzowicz, Evangelos Kranakis, Jorge Urrutia:
  Guarding the Convex Subsets of a Point-set.
  
• Peter Anderson, Alejandro López-Ortiz:
  A New Lower Bound for Kernel Searching.
  

Session C3.1: Polyhedra

• Komei Fukuda, Thomas M. Liebling, Christine Lütolf:
  Extended Convex Hull.
  
• Sonoko Moriyama, Fumihiko Takeuchi:
  Incremental construction properties in dimension two-- shellability, extendable shellability and vertex decomposability.
  
• Christian Sohler, Martin Ziegler:
  Computing Cut Numbers.
  
• Boting Yang, Cao An Wang:
  Minimal Tetrahedralizations of a Class of Polyhedra.
  

Session C3.2: Geometric Graphs

• José Cáceres, Clara I. Grima, Alberto Márquez:
  Spanners in l₁.
  
• Shin-ichi Tokunaga:
  On a straight-line embedding problem of forests.
  
• S. V. Rao, Asish Mukhopadhyay:
  Efficient Algorithms for Computing the beta-spectrum.
  

Session C4: Voronoi and Relatives

• Nina Amenta, Ravi Krishna Kolluri:
  The Medial Axis of a Union of Balls.
  
• Martin Held:
  Computing Voronoi Diagrams of Line Segments Reliably and Efficiently.
  
• Guilherme Albuquerque Pinto, Pedro Jussieu de Rezende:
  Additively Weighted Voronoi Diagram on the Oriented Projective Plane.
  
• Mordecai J. Golin, Hyeon-Suk Na:
  On the Average Complexity of 3D-Voronoi Diagrams of Random Points on Convex Polytopes.
  

Session I2: Paul Erdos Memorial Lecture

• Gil Kalai:
  Fractional Helly theorem, weak epsilon nets and geometric piercing.
  

Session C5.1: Robustness

• Biliana Kaneva, Joseph O'Rourke:
  An Implementation of Chen & Han's Shortest Paths Algorithm.
  
• Jean-Daniel Boissonnat, Antoine Vigneron:
  An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments.
  
• Dominique Michelucci, Jean-Michel Moreau:
  ZEA - A zero-free exact arithmetic .
  

Session C5.2: Area and Volume

• Ralph P. Boland, Jorge Urrutia:
  Polygon Area Problems.
  
• Hannah Bast, Susan Hert:
  The Area Partitioning Problem.
  
• Therese C. Biedl:
  1-bend 3-D orthogonal drawings: two open problems solved.
  

Session C6.1: Queries in High Dimensions

• John Iacono, Stefan Langerman:
  Dynamic point location in fat hyperrectangles with integer coordinates.
  
• Bradford G. Nickerson, Yunlan Pan:
  On Dynamic k-d Half-Space Range Reporting.
  
• Mary Inaba, Hiroshi Imai:
  Finding k-Closest-Pairs Efficiently for High Dimensional Data.
  
• Mario A. Lopez, Swanwa Liao:
  Finding k-Closest-Pairs Efficiently for High Dimensional Data.
  

Session C6.2: Block Pushing, Discrete Geometry

• Michael Hoffmann:
  Push-* is NP-hard.
  
• Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke:
  PushPush and Push-1 are NP-hard in 2D.
  
• Manuela Neagu:
  Equivalence of Arrangements of Curves.
  
• Christophe Lemaire, Jean-Christophe Weill:
  Partitioning the sphere with constant area quadrangles.
  

Session C7: Triangulations

• Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl:
  Enumerating Triangulation Paths.
  
• Siu-Wing Cheng, Sheung-Hung Poon:
  Selecting Independent Chains on a Triangulated 2-Manifold.
  
• Martin Isenburg, Jack Snoeyink:
  Spirale Reversi: Reverse Decoding of the Edgebreaker Encoding.
  
• Andrzej Szymczak, Davis King, Jarek Rossignac:
  An Edgebreaker-Based Efficient Compression Scheme for Connectivity of Regular Meshes.
  

Session I3: IVS-NVision Annual Lecture

• Colin Ware:
  Mapping Data to Dimensions of Perceptual Space.
  

Session O1: Open Problems and Planning

• Erik D. Demaine, Joseph O'Rourke:
  Session O1: Open Problems and Planning.