This list is also available as a BibTeX file.

CCCG 2002 Papers

1

Stan Wagon.
A machine resolution of a four-color hoax.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 174-185, 2002.
URL http://www.cccg.ca/proceedings/2002/stan.ps.

2

Ulrich Kortenkamp.
Cinderella: Computation, complexity, geometry.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 186-191, 2002.
URL http://www.cccg.ca/proceedings/2002/ulrich.pdf.

3

Luc Devroye.
Paul Erdös memorial lecture.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), 2002.
URL http://www.cccg.ca/proceedings/2002/luc.ps.

4

Erik D. Demaine, John Iacono, and Stefan Langerman.
Proximate point searching.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 1-4, 2002.
URL http://www.cccg.ca/proceedings/2002/22.ps.

5

Valentina Damerow, Lukas Finschi, and Martin Ziegler.
Point location algorithms of minimum size.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 5-9, 2002.
URL http://www.cccg.ca/proceedings/2002/08.ps.
URL (Long Version) http://www.cccg.ca/proceedings/2002/08l.ps.

6

Asish Mukhopadhyay.
Using simplicial partitions to determine a closest point to a query line.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 10-12, 2002.
URL http://www.cccg.ca/proceedings/2002/06.ps.

7

Steph Durocher and David Kirkpatrick.
On the hardness of turn-angle-restricted rectilinear cycle cover problems.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 13-16, 2002.
URL http://www.cccg.ca/proceedings/2002/05.ps.

8

Prosenjit Bose, Joachim Gudmundsson, and Pat Morin.
Ordered theta graphs.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 17-21, 2002.
URL http://www.cccg.ca/proceedings/2002/34.ps.

9

Jens-Michael Wierum.
Logarithmic path-length in space-filling curves.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 22-26, 2002.
URL http://www.cccg.ca/proceedings/2002/27.ps.
URL (Long Version) http://www.cccg.ca/proceedings/2002/27l.ps.

10

Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint.
On flat-state connectivity of chains with fixed acute angles.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 27-30, 2002.
URL http://www.cccg.ca/proceedings/2002/16.ps.

11

Erik D. Demaine, Robert A. Hearn, and Michael Hoffman.
Push-2-f is pspace-complete.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 31-35, 2002.
URL http://www.cccg.ca/proceedings/2002/31.ps.

12

Benjamin Marlin and Godfried Toussaint.
Constructing convex 3-polytopes from two triangulations of a polygon.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 36-39, 2002.
URL http://www.cccg.ca/proceedings/2002/28.ps.
URL (Long Version) http://www.cccg.ca/proceedings/2002/28l.ps.

13

I. Boada, N. Coll, and J. A. Sellarès.
Hierarchical planar voronoi diagram approximations.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 40-44, 2002.
URL http://www.cccg.ca/proceedings/2002/17.ps.

14

Joachim Giesen and Matthias John.
The complexity of flow diagrams in the plane.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 45-48, 2002.
URL http://www.cccg.ca/proceedings/2002/30.ps.

15

M. Gopi.
On sampling and reconstructing surfaces with boundaries.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 49-53, 2002.
URL http://www.cccg.ca/proceedings/2002/19.ps.

16

K. Elbassioni, A. Elmasry, and I. Kamel.
Efficient answering of polyhedral queries in r^<i>d</i> using bbs-trees.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 54-57, 2002.
URL http://www.cccg.ca/proceedings/2002/01.ps.

17

Mario A. Lopez and Bradford G. Nickerson.
Analysis of half-space range search using the <i>k</i>-d search skip list.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 58-62, 2002.
URL http://www.cccg.ca/proceedings/2002/25.ps.

18

Michael Hoffmann and Csaba D. Tóth.
Connecting points in the presence of obstacles in the plane.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 63-67, 2002.
URL http://www.cccg.ca/proceedings/2002/18.ps.

19

Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, and Godfried T. Toussaint.
Computing signed permutations of polygons.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 68-71, 2002.
URL http://www.cccg.ca/proceedings/2002/23m.ps.
URL (Long Version) http://www.cccg.ca/proceedings/2002/23l.ps.

20

Francois Anton, David Kirkpatrick, and Darka Mioc.
An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 72-76, 2002.
URL http://www.cccg.ca/proceedings/2002/21.ps.

21

Zhenming Chen and Jinhui Xu.
Robust algorithm for $k$-gon voronoi diagram construction.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 77-81, 2002.
URL http://www.cccg.ca/proceedings/2002/24new.ps.

22

M. L. Gavrilova.
A reliable algorithm for computing the generalized voronoi diagram for a set of spheres in the euclidean <i>d</i>-dimensional space.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 82-87, 2002.
URL http://www.cccg.ca/proceedings/2002/33.ps.

23

Leonard Hagger and Ian Sanders.
Partitioning a deformed urban grid.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 88-92, 2002.
URL http://www.cccg.ca/proceedings/2002/12.ps.
URL (Long Version) http://www.cccg.ca/proceedings/2002/12l.ps.

24

Mirela Damian-Iordache.
Exact and approximation algorithms for computing <i>a</i>-fat decompositions.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 93-96, 2002.
URL http://www.cccg.ca/proceedings/2002/15.ps.

25

Joseph O'Rourke and Geetika Tewari.
Partitioning orthogonal polygons into fat rectangles in polynomial time.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 97-100, 2002.
URL http://www.cccg.ca/proceedings/2002/04.ps.

26

Melody Donoso and Joseph O'Rourke.
Nonorthogonal polyhedra built from rectangles.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 101-104, 2002.
URL http://www.cccg.ca/proceedings/2002/14.ps.

27

Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, and Ming wei Wang.
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 105-108, 2002.
URL http://www.cccg.ca/proceedings/2002/C95.ps.

28

Hervé Brönnimann, Marc Glisse, and David R. Wood.
Cost-optimal quadtrees for ray shooting.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 109-112, 2002.
URL http://www.cccg.ca/proceedings/2002/29.ps.

29

H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides.
On the number of lines tangent to four convex polyhedra.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 113-117, 2002.
URL http://www.cccg.ca/proceedings/2002/C96.ps.

30

Sergei Bespamyatnikh.
Computing closest points for segments.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 118-122, 2002.
URL http://www.cccg.ca/proceedings/2002/20.ps.

31

Joao Dinis and Margarida Mamede.
A sweep line algorithm for nearest neighbour queries.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 123-127, 2002.
URL http://www.cccg.ca/proceedings/2002/07.ps.

32

Anil Maheshwari, Jan Vahrenhold, and Norbert Zeh.
On reverse nearest neighbor queries.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 128-132, 2002.
URL http://www.cccg.ca/proceedings/2002/32.ps.

33

P. H. Huang, Y. T. Tsai, and C. Y. Tang.
A near-quadratic algorithm for the alpha-connected two-center decision problem.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 133-136, 2002.
URL http://www.cccg.ca/proceedings/2002/36.ps.

34

T. Biedl, M. Hasan, J. D. Horton, A. López-Ortiz, and T. Vinar.
Searching for the center of a circle.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 137-141, 2002.
URL http://www.cccg.ca/proceedings/2002/C98.ps.

35

Prosenjit Bose, Michiel Smid, and David R. Wood.
Light edges in degree-constrained graphs.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 142-145, 2002.
URL http://www.cccg.ca/proceedings/2002/35.ps.

36

Therese Biedl, Timothy M. Chan, and Alejandro López-Ortiz.
Drawing <i>k</i>₂,<i>n</i>: A lower bound.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 146-148, 2002.
URL http://www.cccg.ca/proceedings/2002/C99.ps.

37

Emilio Di Giacomo, Giuseppe Liotta, and Stephen K. Wismath.
Drawing series-parallel graphs on a box.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 149-153, 2002.
URL http://www.cccg.ca/proceedings/2002/C97.ps.

38

Masud Hasan, Md. Saidur Rahman, and Takao Nishizeki.
A linear algorithm for compact box-drawings of trees.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 154-157, 2002.
URL http://www.cccg.ca/proceedings/2002/C94.ps.

39

Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, and Bettina Speckmann.
Convexity minimizes pseudo-triangulations.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 158-161, 2002.
URL http://www.cccg.ca/proceedings/2002/03.ps.

40

Sergei Bespamyatnikh.
Enumerating pseudo-triangulations in the plane.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 162-166, 2002.
URL http://www.cccg.ca/proceedings/2002/10.ps.

41

David Orden and Francisco Santos.
Asymptotically efficient triangulations of the <i>d</i>-cube.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 167-169, 2002.
URL http://www.cccg.ca/proceedings/2002/02.ps.

42

Frederick Crimins and Diane Souvaine.
Constructing differentiable homeomorphisms between isomorphic triangulations.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pages 170-173, 2002.
URL http://www.cccg.ca/proceedings/2002/13.ps.

43

Erik Demaine and Joseph O'Rourke.
Open problems from cccg 2001.
In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), 2002.
URL http://www.cs.uleth.ca/~wismath/cccg/papers/open.ps.
URL (Long Version) http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.