Proceedings of the 14th Canadian Conference on Computational Geometry
University of Lethbridge, August 12-14, 2002
Editor: Stephen Wismath

Preface:
[ p. i ]

Invited Talks

A Machine Resolution of a Four-Color Hoax
Stan Wagon
p. 174-185
[ Short version ]

Cinderella: Computation, Complexity, Geometry
Ulrich Kortenkamp
p. 186-191
[ Short version ]

Paul Erdös Memorial Lecture
Luc Devroye
p. 192
[ Short version ]

Contributed Papers

Proximate Point Searching
Erik D. Demaine, John Iacono, Stefan Langerman
p. 1-4
[ Short version ]

Point Location Algorithms of Minimum Size
Valentina Damerow, Lukas Finschi, Martin Ziegler
p. 5-9
[ Short version ] [ Long version ]

Using Simplicial Partitions to Determine a Closest Point to a Query Line
Asish Mukhopadhyay
p. 10-12
[ Short version ]

On the Hardness of Turn-Angle-Restricted Rectilinear Cycle Cover Problems
Steph Durocher, David Kirkpatrick
p. 13-16
[ Short version ]

Ordered Theta Graphs
Prosenjit Bose, Joachim Gudmundsson, Pat Morin
p. 17-21
[ Short version ]

Logarithmic Path-Length in Space-Filling Curves
Jens-Michael Wierum
p. 22-26
[ Short version ] [ Long version ]

On Flat-State Connectivity of Chains with Fixed Acute Angles
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint
p. 27-30
[ Short version ]

PUSH-2-F is PSPACE-Complete
Erik D. Demaine, Robert A. Hearn, Michael Hoffman
p. 31-35
[ Short version ]

Constructing Convex 3-Polytopes from Two Triangulations of a Polygon
Benjamin Marlin, Godfried Toussaint
p. 36-39
[ Short version ] [ Long version ]

Hierarchical Planar Voronoi Diagram Approximations
I. Boada, N. Coll, J. A. Sellarès
p. 40-44
[ Short version ]

The Complexity of Flow Diagrams in the Plane
Joachim Giesen, Matthias John
p. 45-48
[ Short version ]

On Sampling and Reconstructing Surfaces with Boundaries
M. Gopi
p. 49-53
[ Short version ]

Efficient Answering of Polyhedral Queries in R^d Using BBS-Trees
K. Elbassioni, A. Elmasry, I. Kamel
p. 54-57
[ Short version ]

Analysis of Half-Space Range Search Using the k-d Search Skip List
Mario A. Lopez, Bradford G. Nickerson
p. 58-62
[ Short version ]

Connecting Points in the Presence of Obstacles in the Plane
Michael Hoffmann, Csaba D. Tóth
p. 63-67
[ Short version ]

Computing Signed Permutations of Polygons
Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
p. 68-71
[ Short version (modified slightly from proc.) ] [ Long version ]

An Exact Algebraic Predicate for Maintaining the Topology of the Voronoi Diagram for Circles
Francois Anton, David Kirkpatrick, Darka Mioc
p. 72-76
[ Short version ]

Robust Algorithm for k-Gon Voronoi Diagram Construction
Zhenming Chen, Evanthia Papadopoulou, Jinhui Xu
(N.b. Slightly modified from hardcopy proceedings)
p. 77-81
[ Short version ]

A Reliable Algorithm for Computing the Generalized Voronoi Diagram for a Set of Spheres in the Euclidean d-dimensional Space
M. L. Gavrilova
p. 82-87
[ Short version ]

Partitioning a Deformed Urban Grid
Leonard Hagger, Ian Sanders
p. 88-92
[ Short version ] [ Long version ]

Exact and Approximation Algorithms for Computing a-fat Decompositions
Mirela Damian-Iordache
p. 93-96
[ Short version ]

Partitioning Orthogonal Polygons into Fat Rectangles in Polynomial Time
Joseph O'Rourke, Geetika Tewari
p. 97-100
[ Short version ]

Nonorthogonal Polyhedra Built from Rectangles
Melody Donoso, Joseph O'Rourke
p. 101-104
[ Short version ]

Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, Ming-wei Wang
p. 105-108
[ Short version ]

Cost-Optimal Quadtrees for Ray Shooting
Hervé Brönnimann, Marc Glisse, David R. Wood
p. 109-112
[ Short version ]

On the Number of Lines Tangent to Four Convex Polyhedra
H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, S. Whitesides
p. 113-117
[ Short version ]

Computing Closest Points for Segments
Sergei Bespamyatnikh
p. 118-122
[ Short version ]

A Sweep Line Algorithm for Nearest Neighbour Queries
Joao Dinis, Margarida Mamede
p. 123-127
[ Short version ]

On Reverse Nearest Neighbor Queries
Anil Maheshwari, Jan Vahrenhold, Norbert Zeh
p. 128-132
[ Short version ]

A Near-Quadratic Algorithm for the Alpha-Connected Two-Center Decision Problem
P. H. Huang, Y. T. Tsai, C. Y. Tang
p. 133-136
[ Short version ]

Searching for the Center of a Circle
T. Biedl, M. Hasan, J. D. Horton, A. López-Ortiz, T. Vinar
p. 137-141
[ Short version ]

Light Edges in Degree-Constrained Graphs
Prosenjit Bose, Michiel Smid, David R. Wood
p. 142-145
[ Short version ]

Drawing K₂,n: A Lower Bound
Therese Biedl, Timothy M. Chan, Alejandro López-Ortiz
p. 146-148
[ Short version ]

Drawing Series-Parallel Graphs on a Box
Emilio Di Giacomo, Giuseppe Liotta, Stephen K. Wismath
p. 149-153
[ Short version ]

A Linear Algorithm for Compact Box-Drawings of Trees
Masud Hasan, Md. Saidur Rahman, Takao Nishizeki
p. 154-157
[ Short version ]

Convexity Minimizes Pseudo-Triangulations
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann
p. 158-161
[ Short version ]

Enumerating Pseudo-Triangulations in the Plane
Sergei Bespamyatnikh
p. 162-166
[ Short version ]

Asymptotically Efficient Triangulations of the d-cube
David Orden, Francisco Santos
p. 167-169
[ Short version ]

Constructing Differentiable Homeomorphisms Between Isomorphic Triangulations
Frederick Crimins, Diane Souvaine
p. 170-173
[ Modified from the conference version ] [ as above in pdf]

Open Problems from CCCG 2001
Erik Demaine, Joseph O'Rourke
(Does not appear in hard copy proceedings)
[ postscript ] [ pdf ]