This list is also available as a BibTeX file. The entire collection of short abstracts is available as a PDF file.

CCCG 2008 Papers

1

Ron Graham.
Paul Erdös memorial lecture: Iterated partitions of triangles.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), page 1, 2008.
URL http://cccg.ca/proceedings/2008/invited01.pdf.

2

Michael I. Shamos.
How did it start?
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), page 3, 2008.
URL http://cccg.ca/proceedings/2008/invited02.pdf.

3

Dmitri Tymoczko.
The geometry of music.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), page 5, 2008.
URL http://cccg.ca/proceedings/2008/invited03.pdf.

4

Ravi Janardan, Prosenjit Gupta, Yokesh Kumar, and Michiel Smid.
Data structures for range-aggregate extent queries.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 7-10, 2008.
URL http://cccg.ca/proceedings/2008/paper01.pdf.
URL http://cccg.ca/proceedings/2008/paper01full.pdf.

5

Marek Karpinski and Yakov Nekrich.
Searching for frequent colors in rectangles.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 11-14, 2008.
URL http://cccg.ca/proceedings/2008/paper02.pdf.
URL http://cccg.ca/proceedings/2008/paper02full.pdf.

6

Mashhood Ishaque, Diane Souvaine, and Nadia Benbernou.
Data structures for restricted triangular range searching.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 15-18, 2008.
URL http://cccg.ca/proceedings/2008/paper03.pdf.
URL http://cccg.ca/proceedings/2008/paper03full.pdf.

7

Gerhard Guettler and Colin Mallows.
A generalization of apollonian packing of circles.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 19-22, 2008.
URL http://cccg.ca/proceedings/2008/paper04.pdf.
URL http://cccg.ca/proceedings/2008/paper04full.pdf.

8

Svetlana Stolpner, Jonathan Lenchner, Giuseppe Liotta, David Bremner, Christophe Paul, Marc Pouget, and Stephen Wismath.
A note on $\alpha$-drawable $k$-trees.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 23-26, 2008.
URL http://cccg.ca/proceedings/2008/paper05.pdf.
URL http://cccg.ca/proceedings/2008/paper05full.pdf.

9

James King.
Vc-dimension of visibility on terrains.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 27-30, 2008.
URL http://cccg.ca/proceedings/2008/paper06.pdf.
URL http://cccg.ca/proceedings/2008/paper06full.pdf.

10

Ryuhei Uehara.
Polygons folding to plural incongruent orthogonal boxes.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 31-34, 2008.
URL http://cccg.ca/proceedings/2008/paper07.pdf.
URL http://cccg.ca/proceedings/2008/paper07full.pdf.

11

Alex Benton and Joseph O'Rourke.
A class of convex polyhedra with few edge unfoldings.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 35-38, 2008.
URL http://cccg.ca/proceedings/2008/paper08.pdf.
URL http://cccg.ca/proceedings/2008/paper08full.pdf.

12

Youichi Fujimoto, Mitsuo Motoki, and Ryuhei Uehara.
Inverting linkages with stretch.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 39-42, 2008.
URL http://cccg.ca/proceedings/2008/paper09.pdf.

13

Deepanjan Kesh and Shashank Mehta.
Polynomial irreducibility testing through minkowski summand computation.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 43-46, 2008.
URL http://cccg.ca/proceedings/2008/paper10.pdf.
URL http://cccg.ca/proceedings/2008/paper10full.pdf.

14

Jérémy Barbay, Eric Y, and Chen.
Convex hull of the union of convex objects in the plane: an adaptive analysis.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 47-50, 2008.
URL http://cccg.ca/proceedings/2008/paper11.pdf.
URL http://cccg.ca/proceedings/2008/paper11full.pdf.

15

Mojtaba Nouri Bygi and Mohammad Ghodsi.
Polar diagram of moving objects.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 51-54, 2008.
URL http://cccg.ca/proceedings/2008/paper12.pdf.
URL http://cccg.ca/proceedings/2008/paper12full.pdf.

16

Prosenjit Bose, Joseph O'Rourke, Chang Shu, and Stefanie Wuhrer.
Isometric morphing of triangular meshes.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 55-58, 2008.
URL http://cccg.ca/proceedings/2008/paper13.pdf.
URL http://cccg.ca/proceedings/2008/paper13full.pdf.

17

Christian Wulff-Nilsen.
Computing the stretch factor of paths, trees, and cycles in weighted fixed orientation metrics.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 59-62, 2008.
URL http://cccg.ca/proceedings/2008/paper14.pdf.
URL http://cccg.ca/proceedings/2008/paper14full.pdf.

18

Manjish Pal.
The focus of attention problem revisited.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 63-66, 2008.
URL http://cccg.ca/proceedings/2008/paper15.pdf.
URL http://cccg.ca/proceedings/2008/paper15full.pdf.

19

Adrian Dumitrescu.
On distinct distances among points in general position and other related problems.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 67-70, 2008.
URL http://cccg.ca/proceedings/2008/paper16.pdf.

20

Adrian Dumitrescu and Minghui Jiang.
Monochromatic simplices of any volume.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 71-74, 2008.
URL http://cccg.ca/proceedings/2008/paper17.pdf.

21

Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Pe naloza, Thomas Hackl, Clemens Huemer, and Jorge Urrutia.
Empty monochromatic triangles.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 75-78, 2008.
URL http://cccg.ca/proceedings/2008/paper18.pdf.
URL http://cccg.ca/proceedings/2008/paper18full.pdf.

22

Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, and Joseph O'Rourke.
Draining a polygon-or-rolling a ball out of a polygon.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 79-82, 2008.
URL http://cccg.ca/proceedings/2008/paper19.pdf.

23

Eric McCreath.
Partial matching of planar polygons under translation and rotation.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 83-86, 2008.
URL http://cccg.ca/proceedings/2008/paper20.pdf.
URL http://cccg.ca/proceedings/2008/paper20full.pdf.

24

Subhas Nandy, Krishnendu Mukhopadhyaya, and Bhargab B. Bhattacharya.
Recognition of largest empty orthoconvex polygon in a point set.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 87-90, 2008.
URL http://cccg.ca/proceedings/2008/paper21.pdf.
URL http://cccg.ca/proceedings/2008/paper21full.pdf.

25

Natasa Jovanovic, Jan Korst, and Augustus J.E.M. Janssen.
Minimum blocking sets of circles for a set of lines in the plane.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 91-94, 2008.
URL http://cccg.ca/proceedings/2008/paper22.pdf.
URL http://cccg.ca/proceedings/2008/paper22full.pdf.

26

Mohammad Ali Abam, Mark de Berg, and Sheung-Hung Poon.
Fault-tolerant conflict-free coloring.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 95-98, 2008.
URL http://cccg.ca/proceedings/2008/paper23.pdf.
URL http://cccg.ca/proceedings/2008/paper23full.pdf.

27

Joseph O'Rourke, Perouz Taslakian, and Godfried Toussaint.
A pumping lemma for homometric rhythms.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 99-102, 2008.
URL http://cccg.ca/proceedings/2008/paper24.pdf.
URL http://cccg.ca/proceedings/2008/paper24full.pdf.

28

Priya Ranjan Sinha Mahapatra, Partha P. Goswami, and Sandip Das.
Maximal covering by two isothetic unit squares.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 103-106, 2008.
URL http://cccg.ca/proceedings/2008/paper25.pdf.
URL http://cccg.ca/proceedings/2008/paper25full.pdf.

29

Greg Aloupis, Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman, and Bettina Speckmann.
Triangulating and guarding realistic polygons.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 107-110, 2008.
URL http://cccg.ca/proceedings/2008/paper26.pdf.
URL http://cccg.ca/proceedings/2008/paper26full.pdf.

30

Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovic.
Computing dehn twists and geometric intersection numbers in polynomial time.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 111-114, 2008.
URL http://cccg.ca/proceedings/2008/paper27.pdf.
URL http://cccg.ca/proceedings/2008/paper27full.pdf.

31

Benoît Hudson and Duru Türkoglu.
An efficient query structure for mesh refinement.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 115-118, 2008.
URL http://cccg.ca/proceedings/2008/paper28.pdf.
URL http://cccg.ca/proceedings/2008/paper28full.pdf.

32

Qiaosheng Shi and Binay Bhattacharya.
Application of computational geometry to network $p$-center location problems.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 119-122, 2008.
URL http://cccg.ca/proceedings/2008/paper29.pdf.
URL http://cccg.ca/proceedings/2008/paper29full.pdf.

33

Jihui Zhao and William Steiger.
Generalized ham-sandwich cuts for well separated point sets.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 123-126, 2008.
URL http://cccg.ca/proceedings/2008/paper30.pdf.
URL http://cccg.ca/proceedings/2008/paper30full.pdf.

34

Selim Akl, Kamrul Islam, and Henk Meijer.
Direct planar tree transformation and counterexample.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 127-130, 2008.
URL http://cccg.ca/proceedings/2008/paper31.pdf.
URL http://cccg.ca/proceedings/2008/paper31full.pdf.

35

Dania El-Khechen, John Iacono, Thomas Fevens, and Günter Rote.
Partitioning a polygon into two mirror congruent pieces.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 131-134, 2008.
URL http://cccg.ca/proceedings/2008/paper32.pdf.
URL http://cccg.ca/proceedings/2008/paper32full.pdf.

36

Esther Arkin, George Hart, Joondong Kim, Irina Kostitsyna, Joseph Mitchell, Girishkumar Sabhnani, and Steven Skiena.
The embroidery problem.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 135-138, 2008.
URL http://cccg.ca/proceedings/2008/paper33.pdf.
URL http://cccg.ca/proceedings/2008/paper33full.pdf.

37

Erik D. Demaine, Martin L. Demaine, and Vi Hart.
Computational balloon twisting: The theory of balloon polyhedra.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 139-142, 2008.
URL http://cccg.ca/proceedings/2008/paper34.pdf.
URL http://cccg.ca/proceedings/2008/paper34full.pdf.

38

Henk Meijer, Yurai Nú nez Rodríguez, and David Rappaport.
On the complexity of point recolouring in geometric graphs.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 143-146, 2008.
URL http://cccg.ca/proceedings/2008/paper35.pdf.
URL http://cccg.ca/proceedings/2008/paper35full.pdf.

39

Karim Abu Affash and Matthew J. Katz.
Improved bounds on the average distance to the fermat-weber center of a convex object.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 147-150, 2008.
URL http://cccg.ca/proceedings/2008/paper36.pdf.
URL http://cccg.ca/proceedings/2008/paper36full.pdf.

40

Mohammad Moharrami and Avner Magen.
On the nonexistence of dimension reduction for $\ell^2_2$ metrics.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 151-154, 2008.
URL http://cccg.ca/proceedings/2008/paper37.pdf.
URL http://cccg.ca/proceedings/2008/paper37full.pdf.

41

Mina Razaghpour and Anna Lubiw.
The steiner ratio for obstacle-avoiding rectilinear steiner trees.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 155-158, 2008.
URL http://cccg.ca/proceedings/2008/paper38.pdf.
URL http://cccg.ca/proceedings/2008/paper38full.pdf.

42

Hamid Zarrabi-Zadeh.
Core-preserving algorithms.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 159-162, 2008.
URL http://cccg.ca/proceedings/2008/paper39.pdf.
URL http://cccg.ca/proceedings/2008/paper39full.pdf.

43

Jonathan Derryberry, Don Sheehy, Maverick Woo, and Danny Sleator.
Achieving spatial adaptivity while finding approximate nearest neighbors.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 163-166, 2008.
URL http://cccg.ca/proceedings/2008/paper40.pdf.
URL http://cccg.ca/proceedings/2008/paper40full.pdf.

44

Prosenjit Bose, Stefan Langerman, and Sasanka Roy.
Smallest enclosing circle centered on a query line segment.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 167-170, 2008.
URL http://cccg.ca/proceedings/2008/paper41.pdf.
URL http://cccg.ca/proceedings/2008/paper41full.pdf.

45

Khaled Elbassioni and Hans Raj Tiwary.
On a cone covering problem.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 171-174, 2008.
URL http://cccg.ca/proceedings/2008/paper42.pdf.
URL http://cccg.ca/proceedings/2008/paper42full.pdf.

46

Don Sheehy, Gary Miller, and Todd Phillips.
Linear-size meshes.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 175-178, 2008.
URL http://cccg.ca/proceedings/2008/paper43.pdf.
URL http://cccg.ca/proceedings/2008/paper43full.pdf.

47

Hamid Reza Chitsaz, Steven M. LaValle, and Jason O'Kane.
Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 179-182, 2008.
URL http://cccg.ca/proceedings/2008/paper44.pdf.
URL http://cccg.ca/proceedings/2008/paper44full.pdf.

48

Erik Demaine and Joseph O'Rourke.
Open problems from cccg 2007.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 183-186, 2008.
URL http://cccg.ca/proceedings/2008/paper45.pdf.
URL http://cccg.ca/proceedings/2008/paper45full.pdf.

49

Ovidiu Daescu and Anastasia Kurdia.
Polygonal chain simplification with small angle constraints.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 191-194, 2008.
URL http://cccg.ca/proceedings/2008/paper46.pdf.
URL http://cccg.ca/proceedings/2008/paper46full.pdf.

50

Maia Fraser, Evangelos Kranakis, and Jorge Urrutia.
Memory requirements for local geometric routing and traversal in digraphs.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 195-198, 2008.
URL http://cccg.ca/proceedings/2008/paper47.pdf.
URL http://cccg.ca/proceedings/2008/paper47full.pdf.

51

Yurai Nú nez Rodríguez, Henry Xiao, Kamrul Islam, and Waleed Alsalih.
A distributed algorithm for computing voronoi diagram in the unit disk graph model.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 199-202, 2008.
URL http://cccg.ca/proceedings/2008/paper48.pdf.
URL http://cccg.ca/proceedings/2008/paper48full.pdf.

52

Stefan Näher and Daniel Schmitt.
A framework for multi-core implementations of divide and conquer algorithms and its application to the convex hull problem.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 203-206, 2008.
URL http://cccg.ca/proceedings/2008/paper49.pdf.
URL http://cccg.ca/proceedings/2008/paper49full.pdf.

53

Jeff Sember and William Evans.
Guaranteed voronoi diagrams of uncertain sites.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 207-210, 2008.
URL http://cccg.ca/proceedings/2008/paper50.pdf.
URL http://cccg.ca/proceedings/2008/paper50full.pdf.

54

Joachim Giesen, Madhusudan Manjunath, and Michael Eigensatz.
The solution path of the slab support vector machine.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 211-214, 2008.
URL http://cccg.ca/proceedings/2008/paper51.pdf.
URL http://cccg.ca/proceedings/2008/paper51full.pdf.

55

Reza Dorrigiv and Alejandro López-Ortiz.
Adaptive searching in one and two dimensions.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 215-218, 2008.
URL http://cccg.ca/proceedings/2008/paper52.pdf.

56

Peter Damaschke.
Competitive search for longest empty intervals.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 219-222, 2008.
URL http://cccg.ca/proceedings/2008/paper53.pdf.
URL http://cccg.ca/proceedings/2008/paper53full.pdf.

57

Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane Souvaine, and Csaba Toth.
Erratum for ``disjoint segments have convex partitions with 2-edge connected dual graphs''.
In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 223-226, 2008.
URL http://cccg.ca/proceedings/2008/paper54.pdf.
URL http://cccg.ca/proceedings/2008/paper54full.pdf.