This list is also available as a BibTeX file.

CCCG 2004 Papers

1

Adrian Dumitrescu.
A remark on the Erdös-Szekeres theorem.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 2-3, 2004.
URL http://www.cccg.ca/proceedings/2004/6.pdf.
URL http://www.cccg.ca/proceedings/2004/6.ps.

2

Khaled Elbassioni, Amr Elmasry, and Vladimir Gurvich.
A stronger version of bárány's theorem in the plane.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 4-6, 2004.
URL http://www.cccg.ca/proceedings/2004/17.pdf.
URL http://www.cccg.ca/proceedings/2004/17.ps.

3

Gruia Calinescu, Adrian Dumitrescu, and Peng-Jun Wan.
Separating points by axis-parallel lines.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 7-10, 2004.
URL http://www.cccg.ca/proceedings/2004/11.pdf.
URL http://www.cccg.ca/proceedings/2004/11.ps.

4

Joachim Giesen and Simon Spalinger.
Meshless surface reconstruction by kernel clustering.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 11-14, 2004.
URL http://www.cccg.ca/proceedings/2004/33.pdf.
URL http://www.cccg.ca/proceedings/2004/33.ps.

5

Daniel Freedman.
Surface reconstruction, one triangle at a time.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 15-19, 2004.
URL http://www.cccg.ca/proceedings/2004/9.pdf.
URL http://www.cccg.ca/proceedings/2004/9.ps.

6

Mirela Damian and Joseph O'Rourke.
On corners of objects built from parallelepiped bricks.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 20-23, 2004.
URL http://www.cccg.ca/proceedings/2004/47.pdf.
URL http://www.cccg.ca/proceedings/2004/47.ps.

7

Benoit Hudson and Gary Miller.
Using bistellar flips for rotations in point location structures.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 29-32, 2004.
URL http://www.cccg.ca/proceedings/2004/52.pdf.
URL http://www.cccg.ca/proceedings/2004/52.ps.

8

Stephan Foldes.
Decomposition of planar motions into reflections and rotations with distance constraints.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 33-35, 2004.
URL http://www.cccg.ca/proceedings/2004/31.pdf.
URL http://www.cccg.ca/proceedings/2004/31.ps.

9

Valentin Polishchuk.
The box mover problem.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 36-39, 2004.
URL http://www.cccg.ca/proceedings/2004/43.pdf.
URL http://www.cccg.ca/proceedings/2004/43.ps.

10

Pat Morin and David R. Wood.
Three-dimensional 1-bend graph drawings.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 40-43, 2004.
URL http://www.cccg.ca/proceedings/2004/4.pdf.
URL http://www.cccg.ca/proceedings/2004/4.ps.

11

Andrea Mantler and Jack Snoeyink.
Banana spiders: A study of connectivity in 3d combinatorial rigidity.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 44-47, 2004.
URL http://www.cccg.ca/proceedings/2004/42.pdf.
URL http://www.cccg.ca/proceedings/2004/42.ps.

12

Ferran Hurtado, Mikio Kano, David Rappaport, and Csaba Tóth.
Encompassing colored crossing-free geometric graphs.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 48-52, 2004.
URL http://www.cccg.ca/proceedings/2004/46.pdf.
URL http://www.cccg.ca/proceedings/2004/46.ps.

13

Therese Biedl and Burkay Genc.
When can a graph form an orthogonal polyhedron?
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 53-56, 2004.
URL http://www.cccg.ca/proceedings/2004/15.pdf.
URL http://www.cccg.ca/proceedings/2004/15.ps.

14

Henk Meijer and David Rappaport.
Simultaneous edge flips for convex subdivisions.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 57-59, 2004.
URL http://www.cccg.ca/proceedings/2004/5.pdf.
URL http://www.cccg.ca/proceedings/2004/5.ps.

15

Greg Aloupis, Erik Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint.
Unfolding polyhedral bands.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 60-63, 2004.
URL http://www.cccg.ca/proceedings/2004/45.pdf.
URL http://www.cccg.ca/proceedings/2004/45.ps.

16

Erik D. Demaine, Satyan L. Devadoss, Joseph S.B. Mitchell, and Joseph O'Rourke.
Continuous foldability of polygonal paper.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 64-67, 2004.
URL http://www.cccg.ca/proceedings/2004/55.pdf.
URL http://www.cccg.ca/proceedings/2004/55.ps.

17

Chris Gray and Will Evans.
Optimistic shortest paths on uncertain terrains.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 68-71, 2004.
URL http://www.cccg.ca/proceedings/2004/48.pdf.
URL http://www.cccg.ca/proceedings/2004/48.ps.

18

Jose Antonio Pérez Ruy-Díaz and Mohammed Safar Sideq.
Approximating optimal paths in terrains with weight defined by a piecewise-linear function.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 72-75, 2004.
URL http://www.cccg.ca/proceedings/2004/3.pdf.
URL http://www.cccg.ca/proceedings/2004/3.ps.

19

William Evans Daniel Archambault and David Kirkpatrick.
Computing the set of all distant horizons of a terrain.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 76-79, 2004.
URL http://www.cccg.ca/proceedings/2004/24.pdf.
URL http://www.cccg.ca/proceedings/2004/24.ps.

20

Vamsikrishna Kundeti and Prosenjit Gupta.
Efficient polygon enclosure algorithms for device extraction from VLSI layouts.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 82-85, 2004.
URL http://www.cccg.ca/proceedings/2004/10.pdf.
URL http://www.cccg.ca/proceedings/2004/10.ps.

21

Chris Worman and Mark Watson.
Tiling layouts with dominoes.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 86-90, 2004.
URL http://www.cccg.ca/proceedings/2004/22.pdf.
URL http://www.cccg.ca/proceedings/2004/22.ps.

22

Ivaylo Ilinkin, Ravi Janardan, Michiel Smid, Eric Johnson, Paul Castillo, and Jörg Schwerdt.
Approximating contact-area of supports in layered manufacturing.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 91-94, 2004.
URL http://www.cccg.ca/proceedings/2004/21.pdf.
URL http://www.cccg.ca/proceedings/2004/21.ps.

23

Steven Pav.
An anisotropic cardinality bound for triangulations.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 95-98, 2004.
URL http://www.cccg.ca/proceedings/2004/34.pdf.
URL http://www.cccg.ca/proceedings/2004/34.ps.

24

Michael Burr, Alan Cheng, Ryan Coleman, and Diane Souvaine.
Transformations and algorithms for least sum of squares hypersphere fitting.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 104-107, 2004.
URL http://www.cccg.ca/proceedings/2004/58.pdf.
URL http://www.cccg.ca/proceedings/2004/58.ps.

25

Prosenjit Bose and Marc van Kreveld.
Computing nice sweeps for polyhedra and polygons.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 108-111, 2004.
URL http://www.cccg.ca/proceedings/2004/54.pdf.
URL http://www.cccg.ca/proceedings/2004/54.ps.

26

Robin Flatland.
On sequential triangulations of simple polygons.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 112-115, 2004.
URL http://www.cccg.ca/proceedings/2004/2.pdf.
URL http://www.cccg.ca/proceedings/2004/2.ps.

27

Sandip Das, Partha P. Goswami, and Subhas C. Nandy.
Smallest $k$ point enclosing rectangle of arbitrary orientation.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 116-119, 2004.
URL http://www.cccg.ca/proceedings/2004/29.pdf.
URL http://www.cccg.ca/proceedings/2004/29.ps.

28

Prosenjit Bose, Carlos Seara, and Saurabh Sethia.
On computing enclosing isosceles triangles and related problems.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 120-123, 2004.
URL http://www.cccg.ca/proceedings/2004/38.pdf.
URL http://www.cccg.ca/proceedings/2004/38.ps.

29

Frank Nielsen and Richard Nock.
Approximating smallest enclosing disks.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 124-127, 2004.
URL http://www.cccg.ca/proceedings/2004/16.pdf.
URL http://www.cccg.ca/proceedings/2004/16.ps.

30

Gill Barequet and Vadim Rogol.
Maximizing the area of an axis-symmetric polygon inscribed by a convex polygon.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 128-131, 2004.
URL http://www.cccg.ca/proceedings/2004/27.pdf.
URL http://www.cccg.ca/proceedings/2004/27.ps.

31

Harish Gopala and Pat Morin.
Algorithms for bivariate zonoid depth.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 132-135, 2004.
URL http://www.cccg.ca/proceedings/2004/56.pdf.
URL http://www.cccg.ca/proceedings/2004/56.ps.

32

Michael Burr, Eynat Rafalin, and Diane Souvaine.
Simplicial depth: An improved definition, analysis, and efficiency for the finite sample case.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 136-139, 2004.
URL http://www.cccg.ca/proceedings/2004/49.pdf.
URL http://www.cccg.ca/proceedings/2004/49.ps.

33

Steph Durocher and David Kirkpatrick.
The gaussian centre and the projection centre of a set of points in $r^3$.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 140-144, 2004.
URL http://www.cccg.ca/proceedings/2004/53.pdf.
URL http://www.cccg.ca/proceedings/2004/53.ps.

34

Jean Cardinal, Sébastien Collette, and Stefan Langerman.
Local properties of geometric graphs.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 145-148, 2004.
URL http://www.cccg.ca/proceedings/2004/50.pdf.
URL http://www.cccg.ca/proceedings/2004/50.ps.

35

Bradford Nickerson and Qingxiu Shi.
Tries for combined text and spatial data range search.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 149-153, 2004.
URL http://www.cccg.ca/proceedings/2004/13.pdf.
URL http://www.cccg.ca/proceedings/2004/13.ps.

36

Ding Liu Bernard Chazelle and Avner Magen.
Approximate range searching in higher dimension.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 154-157, 2004.
URL http://www.cccg.ca/proceedings/2004/23.pdf.
URL http://www.cccg.ca/proceedings/2004/23.ps.

37

Sean Falconer and Bradford Nickerson.
On multi-level k-ranges for range search.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 158-161, 2004.
URL http://www.cccg.ca/proceedings/2004/12.pdf.
URL http://www.cccg.ca/proceedings/2004/12.ps.

38

Adrian Dumitrescu and Günter Rote.
On the fréchet distance of a set of curves.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 162-165, 2004.
URL http://www.cccg.ca/proceedings/2004/39.pdf.
URL http://www.cccg.ca/proceedings/2004/39.ps.

39

François Anton and Sergey Bereg.
The fitting line problem in the laguerre geometry.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 166-169, 2004.
URL http://www.cccg.ca/proceedings/2004/41.pdf.
URL http://www.cccg.ca/proceedings/2004/41.ps.

40

David Bremner and David Gay.
Experimental lower bounds for three simplex chirality measures in low dimension.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 170-173, 2004.
URL http://www.cccg.ca/proceedings/2004/37.pdf.
URL http://www.cccg.ca/proceedings/2004/37.ps.

41

Deok-Soo Kim, Youngsong Cho, and Donguk Kim.
Edge-tracing algorithm for euclidean voronoi diagram of 3d spheres.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 176-179, 2004.
URL http://www.cccg.ca/proceedings/2004/28.pdf.
URL http://www.cccg.ca/proceedings/2004/28.ps.

42

Thomas Hain, Athar Ahmad, and David Langan.
Precise flattening of cubic bézier segments.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 180-183, 2004.
URL http://www.cccg.ca/proceedings/2004/36.pdf.
URL http://www.cccg.ca/proceedings/2004/36.ps.

43

Hervé Brönnimann, Olivier Devillers, Sylvain Lazard, and Frank Sottile.
On the number of line tangents to four triangles in three-dimensional space.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 184-187, 2004.
URL http://www.cccg.ca/proceedings/2004/40.pdf.
URL http://www.cccg.ca/proceedings/2004/40.ps.

44

Nathanael Berglund and Andrzej Szymczak.
Making contour trees subdomain-aware.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 188-191, 2004.
URL http://www.cccg.ca/proceedings/2004/44.pdf.
URL http://www.cccg.ca/proceedings/2004/44.ps.

45

Raja Jothi and Balaji Raghavachari.
Degree-bounded minimum spanning trees.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 192-195, 2004.
URL http://www.cccg.ca/proceedings/2004/32.pdf.
URL http://www.cccg.ca/proceedings/2004/32.ps.

46

Susumu Suzuki and Toshihide Ibaraki.
An average running time analysis of a backtracking algorithm to calculate the measure of the union of hyperrectangles in $d$ dimensions.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 196-199, 2004.
URL http://www.cccg.ca/proceedings/2004/26.pdf.
URL http://www.cccg.ca/proceedings/2004/26.ps.

47

Adrian Dumitrescu.
On some monotone path problems in line arrangements.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 200-203, 2004.
URL http://www.cccg.ca/proceedings/2004/8.pdf.
URL http://www.cccg.ca/proceedings/2004/8.ps.

48

Farshad Rostamabadi and Mohammad Ghodsi.
A fast algorithm for updating a labeling to avoid a moving point.
In Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pages 204-208, 2004.
URL http://www.cccg.ca/proceedings/2004/19.pdf.
URL http://www.cccg.ca/proceedings/2004/19.ps.