This list is also available as a BibTeX file.

CCCG 2003 Papers

1

Karen Daniels, Arti Mathur, and Roger Grinde.
A combinatorial maximum cover approach to 2D translational geometric covering.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 2-5, 2003.
URL http://www.cccg.ca/proceedings/2003/15.pdf.
URL http://www.cccg.ca/proceedings/2003/15.ps.

2

Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar Ragde, and Klaus Reinhardt.
On the parameterized complexity of the generalized rush hour puzzle.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 6-9, 2003.
URL http://www.cccg.ca/proceedings/2003/22.pdf.
URL http://www.cccg.ca/proceedings/2003/22.ps.

3

Tetsuo Asano, David Kirkpatrick, and Chee Yap.
Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 10-13, 2003.
URL http://www.cccg.ca/proceedings/2003/54.pdf.
URL http://www.cccg.ca/proceedings/2003/54.ps.

4

Ying Liu and Mikhail Nediak.
Planar case of the maximum box and related problems.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 14-18, 2003.
URL http://www.cccg.ca/proceedings/2003/13.pdf.
URL http://www.cccg.ca/proceedings/2003/13.ps.

5

Kensuke Onishi and Jin ichi Itoh.
Estimation of the necessary number of points in Riemannian Voronoi.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 19-24, 2003.
URL http://www.cccg.ca/proceedings/2003/14.pdf.
URL http://www.cccg.ca/proceedings/2003/14.ps.

6

Anna Medvedeva and Asish Mukhopadhyay.
An implementation of a linear time algorithm for computing the minimum perimeter triangle enclosing a convex polygon.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 25-28, 2003.
URL http://www.cccg.ca/proceedings/2003/26.pdf.
URL http://www.cccg.ca/proceedings/2003/26.ps.

7

Therese Biedl, Anna Lubiw, and Michael J. Spriggs.
Parallel morphing of trees and cycles.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 29-34, 2003.
URL http://www.cccg.ca/proceedings/2003/20.pdf.
URL http://www.cccg.ca/proceedings/2003/20.ps.

8

Weizhao Wang, Xiang-Yang Li, Yu Wang, and Wen-Zhan Song.
The spanning ratios of $\beta$-skeleton.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 35-38, 2003.
URL http://www.cccg.ca/proceedings/2003/7.pdf.
URL http://www.cccg.ca/proceedings/2003/7.ps.

9

Michael J. Spriggs., J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, and Jack Snoeyink.
Approximating the geometric minimum-diameter spanning tree.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 39-42, 2003.
URL http://www.cccg.ca/proceedings/2003/16.pdf.
URL http://www.cccg.ca/proceedings/2003/16.ps.

10

Mirela Damian and Joseph O'Rourke.
Partitioning regular polygons into circular pieces i: Convex partitions.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 43-46, 2003.
URL http://www.cccg.ca/proceedings/2003/27.pdf.
URL http://www.cccg.ca/proceedings/2003/27.ps.

11

Masud Hasan and Anna Lubiw.
Equiprojective polyhedra.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 47-50, 2003.
URL http://www.cccg.ca/proceedings/2003/33.pdf.
URL http://www.cccg.ca/proceedings/2003/33.ps.

12

Helmut Alt, Marc Glisse, and Xavier Goaoc.
On the worst-case complexity of the silhouette of a polytope.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 51-55, 2003.
URL http://www.cccg.ca/proceedings/2003/12.pdf.
URL http://www.cccg.ca/proceedings/2003/12.ps.

13

Suzanne Gallagher and Joseph O'Rourke.
Coloring objects built from bricks.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 56-59, 2003.
URL http://www.cccg.ca/proceedings/2003/25.pdf.
URL http://www.cccg.ca/proceedings/2003/25.ps.

14

Asish Mukhopadhyay and Quanbin Jing.
Encoding quadrilateral meshes.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 60-63, 2003.
URL http://www.cccg.ca/proceedings/2003/8.pdf.
URL http://www.cccg.ca/proceedings/2003/8.ps.

15

Petr Tobola and Karel Nechvile.
Linear binary space partitions and the hierarchy of object classes.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 64-67, 2003.
URL http://www.cccg.ca/proceedings/2003/10.pdf.
URL http://www.cccg.ca/proceedings/2003/10.ps.

16

Eric Chen and Timothy Chan.
A space-efficient algorithm for segment intersection.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 68-71, 2003.
URL http://www.cccg.ca/proceedings/2003/31.pdf.
URL http://www.cccg.ca/proceedings/2003/31.ps.

17

Timothy M. Chan, Alexander Golynski, Alejandro López-Ortiz, and Claude-Guy Quimper.
Curves of width one and the river shore problem.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 73-75, 2003.
URL http://www.cccg.ca/proceedings/2003/18.pdf.
URL http://www.cccg.ca/proceedings/2003/18.ps.

18

Jocelyn Smith and William Evans.
Triangle guarding.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 76-80, 2003.
URL http://www.cccg.ca/proceedings/2003/46.pdf.
URL http://www.cccg.ca/proceedings/2003/46.ps.

19

Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, David Rappaport, and Godfried Toussaint.
Computing the similarity of two melodies.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 81-84, 2003.
URL http://www.cccg.ca/proceedings/2003/42.pdf.
URL http://www.cccg.ca/proceedings/2003/42.ps.

20

Melkemi Mahmoud.
Molecular graphs of a finite points set: a generalization of the Delaunay triangulation.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 85-88, 2003.
URL http://www.cccg.ca/proceedings/2003/47.pdf.
URL http://www.cccg.ca/proceedings/2003/47.ps.

21

Nicolas Grislain and Jonathan Richard Shewchuk.
The strange complexity of constrained Delaunay triangulation.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 89-93, 2003.
URL http://www.cccg.ca/proceedings/2003/39.pdf.
URL http://www.cccg.ca/proceedings/2003/39.ps.

22

Ali Khanban and Abbas Edalat.
Computing Delaunay triangulation with imprecise input data.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 94-97, 2003.
URL http://www.cccg.ca/proceedings/2003/38.pdf.
URL http://www.cccg.ca/proceedings/2003/38.ps.

23

Robert Hearn, Erik Demaine, and Greg Frederickson.
Hinged dissection of polygons is hard.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 98-102, 2003.
URL http://www.cccg.ca/proceedings/2003/45.pdf.
URL http://www.cccg.ca/proceedings/2003/45.ps.

24

Chris Worman.
Decomposing polygons into diameter bounded components.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 103-106, 2003.
URL http://www.cccg.ca/proceedings/2003/9.pdf.
URL http://www.cccg.ca/proceedings/2003/9.ps.

25

Ferran Hurtado, Godfried Toussaint, and Joan Trias.
On polyhedra induced by point sets in space.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 107-110, 2003.
URL http://www.cccg.ca/proceedings/2003/5.pdf.
URL http://www.cccg.ca/proceedings/2003/5.ps.

26

Jaeil Choi and Andrzej Szymczak.
On coherent rotation angles for as-rigid-as-possible shape interpolation.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 111-114, 2003.
URL http://www.cccg.ca/proceedings/2003/43.pdf.
URL http://www.cccg.ca/proceedings/2003/43.ps.

27

Ian Hsieh, Kiat-Choong Chen, and Cao An Wang.
A genetic algorithm for the minimum tetrahedralization of a convex polyhedron.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 115-119, 2003.
URL http://www.cccg.ca/proceedings/2003/29.pdf.
URL http://www.cccg.ca/proceedings/2003/29.ps.

28

Alexander Golynski and David Bremner.
Sufficiently fat polyhedra are not 2-castable.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 120-122, 2003.
URL http://www.cccg.ca/proceedings/2003/44.pdf.
URL http://www.cccg.ca/proceedings/2003/44.ps.

29

Steph Durocher and David Kirkpatrick.
The gaussian centre of a set of mobile points.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 123-127, 2003.
URL http://www.cccg.ca/proceedings/2003/41.pdf.
URL http://www.cccg.ca/proceedings/2003/41.ps.

30

Laxmi Gewali, Joy Bhadury, and Ramaswamy Chandrasekaran.
Network design subject to facility location.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 128-131, 2003.
URL http://www.cccg.ca/proceedings/2003/51.pdf.
URL http://www.cccg.ca/proceedings/2003/51.ps.

31

Pinaki Mitra, Asish Mukhopadhyay, and S. V. Rao.
Computing the closest point to a circle.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 132-135, 2003.
URL http://www.cccg.ca/proceedings/2003/11.pdf.
URL http://www.cccg.ca/proceedings/2003/11.ps.

32

Marina Gavrilova and Sergei Bespamyatnikh.
On exact solution of a point-location problem in a system of d-dimensional hyperbolic surfaces.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 136-139, 2003.
URL http://www.cccg.ca/proceedings/2003/23.pdf.
URL http://www.cccg.ca/proceedings/2003/23.ps.

33

Oswin Aichholzer, David Orden, Francisco Santos, and Bettina Speckmann.
On the number of pseudo-triangulations of certain point sets.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 141-144, 2003.
URL http://www.cccg.ca/proceedings/2003/53.pdf.
URL http://www.cccg.ca/proceedings/2003/53.ps.

34

J. Mark Keil and Tzvetalin Vassilev.
An algorithm for the MaxMin area triangulation of a convex polygon.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 145-149, 2003.
URL http://www.cccg.ca/proceedings/2003/19.pdf.
URL http://www.cccg.ca/proceedings/2003/19.ps.

35

Shiyan Hu.
A constant approximation algorithm for maximum weight triangulation.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 150-154, 2003.
URL http://www.cccg.ca/proceedings/2003/52.pdf.
URL http://www.cccg.ca/proceedings/2003/52.ps.

36

Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, and Csaba David Tóth.
Degree bounds for constrained pseudo-triangulations.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 155-158, 2003.
URL http://www.cccg.ca/proceedings/2003/34.pdf.
URL http://www.cccg.ca/proceedings/2003/34.ps.

37

Erik D. Demaine, Jeff Erickson, and Stefan Langerman.
On the complexity of halfspace volume queries.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 159-160, 2003.
URL http://www.cccg.ca/proceedings/2003/35.pdf.
URL http://www.cccg.ca/proceedings/2003/35.ps.

38

Lingke Bu and Bradford Nickerson.
Multidimensional orthogonal range search using tries.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 161-165, 2003.
URL http://www.cccg.ca/proceedings/2003/28.pdf.
URL http://www.cccg.ca/proceedings/2003/28.ps.

39

David Hart.
Shortest paths in two intersecting pencils of lines.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 166-169, 2003.
URL http://www.cccg.ca/proceedings/2003/48.pdf.
URL http://www.cccg.ca/proceedings/2003/48.ps.

40

T. Kavitha and Kasturi Varadarajan.
On shortest paths in line arrangements.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 170-173, 2003.
URL http://www.cccg.ca/proceedings/2003/17.pdf.
URL http://www.cccg.ca/proceedings/2003/17.ps.

41

Herve Brönnimann, Hazel Everett, Sylvain Lazard, Frank Sottile, and Sue Whitesides.
Transversals to line segments in $\mathbb{R}^3$.
In Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03), pages 174-177, 2003.
URL http://www.cccg.ca/proceedings/2003/50.pdf.
URL http://www.cccg.ca/proceedings/2003/50.ps.