This list is also available as a BibTeX file.

CCCG 2001 Papers

1

Erik D. Demaine, Martin L. Demaine, and Anna Lubiw.
The cccg 2001 logo.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), 2001.
URL http://www.cccg.ca/proceedings/2001/eddemaine-67778.ps.gz.

2

George W. Hart.
Rapid prototyping of geometric models.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 1-4, 2001.
URL http://www.cccg.ca/proceedings/2001/ghart-80755.ps.gz.

3

Mike Lazaridis.
Opportunities for mathematicians in industry and government research.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), 2001.
URL http://www.cccg.ca/proceedings/2001/lazaridis.ps.gz.

4

Neil J. A. Sloane.
Plane packing.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), 2001.
URL http://www.cccg.ca/proceedings/2001/sloane.ps.gz.

5

Hee kap Ahn, Siu wing Cheng, Otfried Cheong, and Jack Snoeyink.
The reflex-free hull.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 9-12, 2001.
URL http://www.cccg.ca/proceedings/2001/snoeyink-66127.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/snoeyink-68900.ps.gz.

6

Oswin Aichholzer, Ferran Hurtado, and Marc Noy.
On the number of triangulations every planar point set must have.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 13-16, 2001.
URL http://www.cccg.ca/proceedings/2001/oaich-7897.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/oaich-10670.ps.gz.

7

Oswin Aichholzer and Hannes Krasser.
The point set order type data base: A collection of applications and results.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 17-20, 2001.
URL http://www.cccg.ca/proceedings/2001/hkrasser-17690.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/hkrasser-20463.ps.gz.

8

Greg Aloupis, Stefan Langerman, Michael Soss, and Godfried Toussaint.
Algorithms for bivariate medians and a fermat-torricelli problem for lines.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 21-24, 2001.
URL http://www.cccg.ca/proceedings/2001/athens-80345.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/athens-83118.ps.gz.

9

Diogo Vieira Andrade and Luiz Henrique de Figueiredo.
Good approximations for the relative neighbourhood graph.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 25-28, 2001.
URL http://www.cccg.ca/proceedings/2001/lhf-96805.ps.gz.

10

Francois Anton, Darka Mioc, and Christopher M. Gold.
Line voronoi diagram based interpolation and application to digital terrain modelling.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 29-32, 2001.
URL http://www.cccg.ca/proceedings/2001/fanton-44121.ps.gz.

11

Laurent Balmelli, Thomas Liebling, and Martin Vetterli.
Computational analysis of 4-8 meshes with application to surface simplification using global error.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 33-36, 2001.
URL http://www.cccg.ca/proceedings/2001/balmelli-42823.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/balmelli-45596.pdf.gz.

12

Ralph P. Boland and Jorge Urrutia.
A simpler circular ray shooting algorithm.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 37-40, 2001.
URL http://www.cccg.ca/proceedings/2001/rboland-92557.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/rboland-95330.ps.gz.

13

Ralph P. Boland and Jorge Urrutia.
Finding the largest axis aligned rectangle in a polygon in o(n log n) time.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 41-44, 2001.
URL http://www.cccg.ca/proceedings/2001/rboland-98103.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/rboland-876.ps.gz.

14

Björn Brodén, Mikael Hammar, and Bengt J. Nilsson.
Guarding lines and 2-link polygons is apx-hard.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 45-48, 2001.
URL http://www.cccg.ca/proceedings/2001/mikael-2351.ps.gz.

15

Suzanne F. Buchele and Angela C. Roles.
Binary space partitioning tree and constructive solid geometry representations for objects bounded by curved surfaces.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 49-52, 2001.
URL http://www.cccg.ca/proceedings/2001/bucheles-48368.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/bucheles-51141.ps.gz.

16

Andrew Y. Cheng and Ming Ouyang.
On algorithms for simplicial depth.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 53-56, 2001.
URL http://www.cccg.ca/proceedings/2001/ouyang-24534.ps.gz.

17

Éric Colin de Verdière, Michel Pocchiola, and Gert Vegter.
Tutte's barycenter method applied to isotopies.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 57-60, 2001.
URL http://www.cccg.ca/proceedings/2001/colin-38575.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/colin-41348.ps.gz.

18

Karen Daniels and Rajasekhar Inkulu.
Translational polygon covering using intersection graphs.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 61-64, 2001.
URL http://www.cccg.ca/proceedings/2001/inkulur-28782.ps.gz.

19

Erik D. Demaine and Michael Hoffmann.
Pushing blocks is np-complete for noncrossing solution paths.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 65-68, 2001.
URL http://www.cccg.ca/proceedings/2001/eddemaine-21938.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/eddemaine-24711.ps.gz.

20

Erik D. Demaine, Stefan Langerman, and Joseph O'Rourke.
Short interlocked linkages.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 69-72, 2001.
URL http://www.cccg.ca/proceedings/2001/eddemaine-27484.ps.gz.

21

Erik D. Demaine and Joseph S. B. Mitchell.
Reaching folded states of a rectangular piece of paper.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 73-75, 2001.
URL http://www.cccg.ca/proceedings/2001/eddemaine-33029.ps.gz.

22

Olivier Devillers and Philippe Guigue.
The shuffling buffer.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 77-80, 2001.
URL http://www.cccg.ca/proceedings/2001/philippe-87012.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/philippe-89785.ps.gz.

23

Olivier Devillers, Ferran Hurtado, Mercè Mora, and Carlos Seara.
Separating several point sets in the plane.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 81-84, 2001.
URL http://www.cccg.ca/proceedings/2001/seara-3649.ps.gz.

24

Tamal K. Dey, Joachim Giesen, and James Hudson.
Decimating samples for mesh simplification.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 85-88, 2001.
URL http://www.cccg.ca/proceedings/2001/tamaldey-72971.ps.gz.

25

Matthew T. Dickerson and Michael T. Goodrich.
Matching points to a convex polygonal boundary.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 89-92, 2001.
URL http://www.cccg.ca/proceedings/2001/goodrich-6599.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/goodrich-9371.ps.gz.

26

Abbas Edalat, André Lieutier, and Elham Kashefi.
The convex hull in a new model of computation.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 93-96, 2001.
URL http://www.cccg.ca/proceedings/2001/andre-lieutier-74799.ps.gz.

27

Lukas Finschi and Komei Fukuda.
Complete combinatorial generation of small point configurations and hyperplane arrangements.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 97-100, 2001.
URL http://www.cccg.ca/proceedings/2001/finschi-1053.ps.gz.

28

Bernd Gärtner and Thomas Herrmann.
Computing the width of a point set in 3-space.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 101-103, 2001.
URL http://www.cccg.ca/proceedings/2001/herrmann-12144.ps.gz.

29

David Hart.
Approximating the shortest path in line arrangements.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 105-108, 2001.
URL http://www.cccg.ca/proceedings/2001/dhart-59460.ps.gz.

30

Michael Hoffmann and Csaba D. Tóth.
Segment endpoint visibility graphs are hamiltonian.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 109-112, 2001.
URL http://www.cccg.ca/proceedings/2001/toth-88310.ps.gz.

31

Jerzy W. Jaromczyk and Yang Wang.
Local optimization of triangular surface meshes for general quadrics in lp norm.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 113-116, 2001.
URL http://www.cccg.ca/proceedings/2001/jurek-34327.ps.gz.

32

Lutz Kettner, David Kirkpatrick, and Bettina Speckmann.
Tight degree bounds for pseudo-triangulations of points.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 117-120, 2001.
URL http://www.cccg.ca/proceedings/2001/speckman-82764.ps.gz.

33

Zhang-Jian Li and Shin ichi Nakano.
Listing all connected plane triangulation.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 121-124, 2001.
URL http://www.cccg.ca/proceedings/2001/kenlee-91259.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/kenlee-94032.ps.gz.

34

Alejandro L'opez-Ortiz and Graeme Sweet.
Parallel searching on a lattice.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 125-128, 2001.
URL http://www.cccg.ca/proceedings/2001/alopez-69253.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/alopez-72026.ps.gz.

35

Andrea Mantler and Jack Snoeyink.
Heaphull?
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 129-131, 2001.
URL http://www.cccg.ca/proceedings/2001/snoeyink-71673.ps.gz.

36

Joseph O'Rourke, Irena Pashchenko, and Geetika Tewari.
Partitioning orthogonal polygons into fat rectangles.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 133-136, 2001.
URL http://www.cccg.ca/proceedings/2001/orourke-18988.ps.gz.

37

Joseph O'Rourke and Octavia Petrovici.
Narrowing light rays with mirrors.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 137-140, 2001.
URL http://www.cccg.ca/proceedings/2001/orourke-13442.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/orourke-13443.ps.gz.

38

Valerio Pascucci.
On the topology of the level sets of a scalar field.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 141-144, 2001.
URL http://www.cccg.ca/proceedings/2001/pascucci-81466.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/pascucci-84239.ps.gz.

39

Axel Pavillet.
Voronoï diagrams in projective geometry and sweep circle algorithms for constructing circle-based voronoï diagrams.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 145-148, 2001.
URL http://www.cccg.ca/proceedings/2001/axel-85891.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/axel.pdf.gz.

40

Dana Randall, Günter Rote, Francisco Santos, and Jack Snoeyink.
Counting triangulations and pseudo-triangulations of wheels.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 149-152, 2001.
URL http://www.cccg.ca/proceedings/2001/snoeyink-77218.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/snoeyink-79991.ps.gz.

41

Ian Sanders and Leigh-Ann Kenny.
Heuristics for placing non-orthogonal axial lines to cross the adjacencies between orthogonal rectangles.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 153-156, 2001.
URL http://www.cccg.ca/proceedings/2001/ian-23236.ps.gz.

42

Chang Shu, Michael Greenspan, and Guy Godin.
Nearest neighbor search through function minimization.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 157-160, 2001.
URL http://www.cccg.ca/proceedings/2001/chang-53914.ps.gz.

43

Jack Snoeyink.
The arithmetic precision of ray-polygon intersection testing.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 161-164, 2001.
URL http://www.cccg.ca/proceedings/2001/snoeyink-9195.ps.gz.

44

Falk Tschirschnitz.
Testing extendability for partial chirotopes is np-complete.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 165-168, 2001.
URL http://www.cccg.ca/proceedings/2001/tschirsc-45242.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/tschirsc-48015.ps.gz.

45

Alper Üngör.
Tiling 3d euclidean space with acute tetrahedra.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 169-172, 2001.
URL http://www.cccg.ca/proceedings/2001/ungor-50788.ps.gz.

46

Chee Yap and Yunyue Zhu.
Yet another look at fractional cascading: B-graphs with application to point location.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 173-176, 2001.
URL http://www.cccg.ca/proceedings/2001/yap-56333.ps.gz.

47

Yunhong Zhou and Subhash Suri.
Geometric permutations of balls with bounded size disparity.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 177-180, 2001.
URL http://www.cccg.ca/proceedings/2001/yzhou-61879.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/yzhou-64652.ps.gz.

48

Martin Ziegler and Vasco Brattka.
Turing computability of (non-)linear optimization.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 181-184, 2001.
URL http://www.cccg.ca/proceedings/2001/ziegler-67425.ps.gz.
URL (Long Version) http://www.cccg.ca/proceedings/2001/ziegler-70198.ps.gz.

49

Erik D. Demaine and Joseph O'Rourke.
Open problems from cccg 2000.
In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pages 185-187, 2001.
URL http://www.cccg.ca/proceedings/2001/eddemaine-18187.ps.gz.