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

Preface:
[ p. i ]


Invited Talks

A Machine Resolution of a FourColor Hoax
Stan Wagon
p. 174185
[ Short version ]

Cinderella: Computation, Complexity, Geometry
Ulrich Kortenkamp
p. 186191
[ 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. 14
[ Short version ]

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

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

On the Hardness of TurnAngleRestricted Rectilinear Cycle Cover Problems
Steph Durocher, David Kirkpatrick
p. 1316
[ Short version ]

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

Logarithmic PathLength in SpaceFilling Curves
JensMichael Wierum
p. 2226
[ Short version ]
[ Long version ]

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

PUSH2F is PSPACEComplete
Erik D. Demaine, Robert A. Hearn, Michael Hoffman
p. 3135
[ Short version ]

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

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

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

On Sampling and Reconstructing Surfaces with Boundaries
M. Gopi
p. 4953
[ Short version ]

Efficient Answering of Polyhedral Queries in R^{d} Using BBSTrees
K. Elbassioni, A. Elmasry, I. Kamel
p. 5457
[ Short version ]

Analysis of HalfSpace Range Search Using the kd Search Skip List
Mario A. Lopez, Bradford G. Nickerson
p. 5862
[ Short version ]

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

Computing Signed Permutations of Polygons
Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
p. 6871
[ 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. 7276
[ Short version ]

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

A Reliable Algorithm for Computing the Generalized Voronoi Diagram for a Set of Spheres in the Euclidean ddimensional Space
M. L. Gavrilova
p. 8287
[ Short version ]

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

Exact and Approximation Algorithms for Computing afat Decompositions
Mirela DamianIordache
p. 9396
[ Short version ]

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

Nonorthogonal Polyhedra Built from Rectangles
Melody Donoso, Joseph O'Rourke
p. 101104
[ 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, Mingwei Wang
p. 105108
[ Short version ]

CostOptimal Quadtrees for Ray Shooting
Hervé Brönnimann, Marc Glisse, David R. Wood
p. 109112
[ 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. 113117
[ Short version ]

Computing Closest Points for Segments
Sergei Bespamyatnikh
p. 118122
[ Short version ]

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

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

A NearQuadratic Algorithm for the AlphaConnected TwoCenter Decision Problem
P. H. Huang, Y. T. Tsai, C. Y. Tang
p. 133136
[ Short version ]

Searching for the Center of a Circle
T. Biedl, M. Hasan, J. D. Horton, A. LópezOrtiz, T. Vinar
p. 137141
[ Short version ]

Light Edges in DegreeConstrained Graphs
Prosenjit Bose, Michiel Smid, David R. Wood
p. 142145
[ Short version ]

Drawing K_{2},n: A Lower Bound
Therese Biedl, Timothy M. Chan, Alejandro LópezOrtiz
p. 146148
[ Short version ]

Drawing SeriesParallel Graphs on a Box
Emilio Di Giacomo, Giuseppe Liotta, Stephen K. Wismath
p. 149153
[ Short version ]

A Linear Algorithm for Compact BoxDrawings of Trees
Masud Hasan, Md. Saidur Rahman, Takao Nishizeki
p. 154157
[ Short version ]

Convexity Minimizes PseudoTriangulations
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann
p. 158161
[ Short version ]

Enumerating PseudoTriangulations in the Plane
Sergei Bespamyatnikh
p. 162166
[ Short version ]

Asymptotically Efficient Triangulations of the dcube
David Orden, Francisco Santos
p. 167169
[ Short version ]

Constructing Differentiable Homeomorphisms Between Isomorphic Triangulations
Frederick Crimins, Diane Souvaine
p. 170173
[ 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 ]
