This list is also available as a BibTeX file.

CCCG 2006 Papers

1

Erick D. Demaine.
Paul Erdos memorial lecture (linkage folding: From erdos to proteins).
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), page 1, 2006.
URL http://cccg.ca/proceedings/2006/cccg1.pdf.

2

Ryuhei Uehara and Sachio Teramoto.
The complexity of a pop-up book.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 3-6, 2006.
URL http://cccg.ca/proceedings/2006/cccg2.pdf.

3

Karen Daniels Wei Li and Konstantin Rybnikov.
A study of conway's thrackle conjecture.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 7-10, 2006.
URL http://cccg.ca/proceedings/2006/cccg3.pdf.

4

Martin L. Demaine Vida Dujmovic Dania El-Khechen Robin Flatland John Iacono Stefan Langerman Henk Meijer Suneeta Ramaswami Diane L. Souvaine Perouz Taslakian Mirela Damian, Erik D. Demaine and Godfried T. Toussaint.
Curves in the sand: Algorithmic drawing.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 11-14, 2006.
URL http://cccg.ca/proceedings/2006/cccg4.pdf.

5

Sada Narayanappa and Petr Vojtechovsky.
An improved approximation factor for the unit disk covering problem.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 15-18, 2006.
URL http://cccg.ca/proceedings/2006/cccg5.pdf.

6

Jan Tusch and Stefan Schirra.
Experimental comparison of the cost of approximate and exact convex hull computation in the plane.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 19-22, 2006.
URL http://cccg.ca/proceedings/2006/cccg6.pdf.

7

Domagoj Matijevic Stefan Funke, Theocharis Malamatos and Nicola Wolpert.
(approximate) conic nearest neighbors and the induced voronoi diagram.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 23-26, 2006.
URL http://cccg.ca/proceedings/2006/cccg7.pdf.

8

Selim G. Akl Md. Kamrul Islam and Henk Meijer.
On planar path transformation.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 27-30, 2006.
URL http://cccg.ca/proceedings/2006/cccg8.pdf.

9

Jonathan Backer and David Kirkpatrick.
Bounded-curvature path normalization.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 31-34, 2006.
URL http://cccg.ca/proceedings/2006/cccg9.pdf.

10

Mustaq Ahmed and Anna Lubiw.
Shortest descending paths through given faces.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 35-38, 2006.
URL http://cccg.ca/proceedings/2006/cccg10.pdf.

11

James King.
Realization of degree 10 minimum spanning trees in 3-space.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 39-42, 2006.
URL http://cccg.ca/proceedings/2006/cccg11.pdf.

12

William Lenhart Jeremy Redburn Hazel Everett, Sylvain Lazard and Linqiao Zhang.
Predicates for line transversals in 3d.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 43-46, 2006.
URL http://cccg.ca/proceedings/2006/cccg12.pdf.

13

Maryam Babazadeh and Hamid Zarrabi-Zadeh.
Small weak epsilon-nets in three dimensions.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 47-50, 2006.
URL http://cccg.ca/proceedings/2006/cccg13.pdf.

14

Junqiang Zhou and Simeon Ntafos.
Two-guard art gallery problem.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 51-54, 2006.
URL http://cccg.ca/proceedings/2006/cccg14.pdf.

15

Qiaosheng Shi Binay Bhattacharya, John Z. Zhang and Tsunehiko Kameda.
An optimal solution to room search problem.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 55-58, 2006.
URL http://cccg.ca/proceedings/2006/cccg15.pdf.

16

Rafa Absar and Sue Whitesides.
On computing shortest external watchman routes for convex polygons.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 59-62, 2006.
URL http://cccg.ca/proceedings/2006/cccg16.pdf.

17

Esther Arkin Valentin Polishchuk and Joseph Mitchell.
Hamiltonian cycles in triangular grids.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 63-66, 2006.
URL http://cccg.ca/proceedings/2006/cccg17.pdf.

18

Yurai Nú nez and David Rappaport.
Tight bounds for point recolouring.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 67-70, 2006.
URL http://cccg.ca/proceedings/2006/cccg18.pdf.

19

Luca Castelli Aleardi Abdelkrim Mebarki and Olivier Devillers.
2d triangulation representation using stable catalogs.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 71-74, 2006.
URL http://cccg.ca/proceedings/2006/cccg19.pdf.

20

Erick D. Demaine and Joseph O'Rourke.
Open problems (open problems from cccg 2005).
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 75-80, 2006.
URL http://cccg.ca/proceedings/2006/cccg20.pdf.

21

Craig Gotsman Gill Barequet and Avishay Sidlesky.
Polygon reconstruction from line cross-sections.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 81-84, 2006.
URL http://cccg.ca/proceedings/2006/cccg21.pdf.

22

David Bremner Prosenjit Bose and Diane L. Souvaine.
Computing the tool path of an externally monotone polygon in linear time.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 85-88, 2006.
URL http://cccg.ca/proceedings/2006/cccg22.pdf.

23

Prosenjit Bose and Jason Morrison.
Optimal polygon placement.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 89-92, 2006.
URL http://cccg.ca/proceedings/2006/cccg23.pdf.

24

Nadia Benbernou and Joseph O'Rourke.
On the maximum span of fixed-angle chains.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 93-96, 2006.
URL http://cccg.ca/proceedings/2006/cccg24.pdf.

25

Brendan Lucier.
Local overlaps in special unfoldings of convex polyhedra.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 97-100, 2006.
URL http://cccg.ca/proceedings/2006/cccg25.pdf.

26

Csaba Tóth and Michael Hoffmann.
Spanning trees across axis-parallel segments.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 101-104, 2006.
URL http://cccg.ca/proceedings/2006/cccg26.pdf.

27

Michiel Smid Prosenjit Bose, Pat Morin and Stefanie Wuhrer.
Rotationally monotone polygons.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 105-108, 2006.
URL http://cccg.ca/proceedings/2006/cccg27.pdf.

28

Joseph O'Rourke Erik D. Demaine, Blaise Gassend and Godfried T. Toussaint.
Polygons flip finitely: Flaws and a fix.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 109-112, 2006.
URL http://cccg.ca/proceedings/2006/cccg28.pdf.

29

John Z. Zhang Tsunehiko Kameda and Masafumi Yamashita.
Characterization of polygons searchable by a boundary 1-searcher.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 113-116, 2006.
URL http://cccg.ca/proceedings/2006/cccg29.pdf.

30

Craig Gotsman Mirela Ben-Chen and Steven Gortler.
Routing with guaranteed delivery on virtual coordinates.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 117-120, 2006.
URL http://cccg.ca/proceedings/2006/cccg30.pdf.

31

Hervé Br Huseyin Akcan.
Practical and efficient geometric epsilon-approximations.

32

Kebin Wang and Shang-Hua Teng.
Geometric separator for $d$-dimensional ball graphs.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 125-128, 2006.
URL http://cccg.ca/proceedings/2006/cccg32.pdf.

33

David Mount.
Invited lecture (on approximate range searching - or - get in shape; round is a good choice).
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), page 129, 2006.
URL http://cccg.ca/proceedings/2006/cccg33.pdf.

34

Frank Nielsen and Richard Nock.
On the smallest enclosing information disk.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 131-134, 2006.
URL http://cccg.ca/proceedings/2006/cccg34.pdf.

35

Pat Morin Rossen Atanassov and Stefanie Wuhrer.
Removing outliers to minimize area and perimeter.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 135-138, 2006.
URL http://cccg.ca/proceedings/2006/cccg35.pdf.

36

Hamid Zarrabi-Zadeh and Timothy Chan.
A simple streaming algorithm for minimum enclosing balls.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 139-142, 2006.
URL http://cccg.ca/proceedings/2006/cccg36.pdf.

37

Jeff M. Phillips and Pankaj K. Agarwal.
On bipartite matching under the rms distance.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 143-146, 2006.
URL http://cccg.ca/proceedings/2006/cccg37.pdf.

38

Bradford Nickerson and Qingxiu Shi.
The pkd-tree for orthogonal $d$-dimensional range search.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 147-150, 2006.
URL http://cccg.ca/proceedings/2006/cccg38.pdf.

39

R. Sharathkumar and Prosenjit Gupta.
Range-aggregate proximity detection for design rule checking in vlsi layouts.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 151-154, 2006.
URL http://cccg.ca/proceedings/2006/cccg39.pdf.

40

Bradford Nickerson and Qingxiu Shi.
K-nearest neighbor search using the pyramid technique.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 155-158, 2006.
URL http://cccg.ca/proceedings/2006/cccg40.pdf.

41

Yakov Nekrich.
A linear space data structure for orthogonal range reporting and emptiness queries.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 159-162, 2006.
URL http://cccg.ca/proceedings/2006/cccg41.pdf.

42

Walter Whiteley.
Invited lecture (predicting the flexibility and rigidity of proteins: Geometry, combinatorics, conjectures, and algorithms).
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), page 163, 2006.
URL http://cccg.ca/proceedings/2006/cccg42.pdf.

43

Maarten van Emden and Belaid Moa.
Computational euclid.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 165-168, 2006.
URL http://cccg.ca/proceedings/2006/cccg43.pdf.

44

Loic Lamarque Dominique Michelucci, Sebti Foufou and David Menegaux.
Another paradigm for geometric constraints solving.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 169-172, 2006.
URL http://cccg.ca/proceedings/2006/cccg44.pdf.

45

Thomas Fevens Dania El-Khechen and John Iacono.
Partitioning a regular $n$-gon into $n+1$ convex congruent pieces is impossible, for sufficiently large $n$.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 173-176, 2006.
URL http://cccg.ca/proceedings/2006/cccg45.pdf.

46

Craig Gotsman and Ian Fischer.
Computing depth contours with graphics hardware.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 177-180, 2006.
URL http://cccg.ca/proceedings/2006/cccg46.pdf.

47

Chris Gray Stephane Durocher and James King.
Minimizing the number of arcs linking a permutation of points in the plane.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 181-184, 2006.
URL http://cccg.ca/proceedings/2006/cccg47.pdf.

48

Asish Mukhopadhyay and R.L. Scot Drysdale.
An $o(n log n)$ algorithm for the all-farthest-segments problem for a planar set of points.
In Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), pages 185-188, 2006.
URL http://cccg.ca/proceedings/2006/cccg48.pdf.