This list is also available as a BibTeX file.

CCCG 2009 Papers

1

Wenqi Ju and Jun Luo.
New algorithms for computing maximum perimeter and maximum area of the convex hull of imprecise inputs based on the parallel line segment model.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 1-4, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_01.pdf.

2

Hee-Kap Ahn, Sang Won Bae, and Iris Reinbacher.
Optimal empty pseudo-triangles in a point set.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 5-8, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_02.pdf.

3

Yves Brise and Bernd G"artner.
Clarkson’s algorithm for violator spaces.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 9-12, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_03.pdf.

4

Christian A. Duncan.
On graph thickness, geometric thickness, and separator theorems.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 13-16, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_04.pdf.

5

Alejandro Estrella-Balderrama, J. Joseph Fowler, and Stephen G. Kobourov.
Colored simultaneous geometric embeddings and universal pointsets.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 17-20, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_05.pdf.

6

Carla Binucci, Emilio Di Giacomo, Walter Didimo, Alejandro Estrella-Balderrama, Fabrizio Frati, Stephen G. Kobourov, and Giuseppe Liotta.
On directed graphs with an upward straight-line.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 21-24, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_06.pdf.

7

Pedro J. Tejada, Xiaojun Qi, and Minghui Jiang.
Computational geometry of contour extraction.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 25-28, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_07.pdf.

8

Takashi HORIYAMA and Masato SAMEJIMA.
Enumeration of polyominoes for p4 tiling.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 29-32, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_08.pdf.

9

Dania El-Khechen, Muriel Dulieu, John Iacono, and Nikolaj van Omme.
Packing $2\times 2$ unit squares into grid polygons is np-complete.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 33-36, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_09.pdf.

10

Misha Kazhdan, Nina Amenta, Shengyin Gu, David F. Wiley, and Bernd Hamann.
Symmetry restoration by stretching.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 37-40, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_10.pdf.

11

J"urgen Bokowski and Vincent Pilaud.
On symmetric realizations of the simplicial complex of 3-crossing-free sets of diagonals of the octagon.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 41-44, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_11.pdf.

12

Md. Shafiul Alam, Asish Mukhopadhyay, and Animesh Sarker.
Generalized jewels and the point placement problem.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 45-48, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_12.pdf.

13

Pavol Hell.
Generalizations of interval graphs.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), page 49, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_13.pdf.

14

Michael D. Adams.
A comparison of two fully-dynamic delaunay triangulation methods.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 51-54, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_14.pdf.

15

Chris Gray, Maarten L"offler, and Rodrigo I. Silveira.
Minimizing slope change in imprecise 1.5d terrains.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 55-58, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_15.pdf.

16

Ahmad Biniaz.
Slope preserving terrain simplification — an experimental study.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 59-62, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_16.pdf.

17

Louis Theran.
Rigid components of random graphs.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 63-66, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_17.pdf.

18

Audrey Lee-St.John and Ileana Streinu.
Angular rigidity in 3d: combinatorial characterizations and algorithms.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 67-70, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_18.pdf.

19

Jialong Cheng, Meera Sitharam, and Ileana Streinu.
Nucleation-free 3d rigidity.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 71-74, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_19.pdf.

20

Erik D. Demaine and Joseph O'Rourke.
Open problems from cccg 2008.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 75-78, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_20.pdf.

21

Gary L. Miller, Todd Phillips, and Donald R. Sheehy.
The centervertex theorem for wedge depth.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 79-82, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_21.pdf.

22

Hamid Zarrabi-Zadeh and Asish Mukhopadhyay.
Streaming 1-center with outliers in high dimensions.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 83-86, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_22.pdf.

23

Tetsuo Asano and G"unter Rote.
Constant-working-space algorithms for geometric problems.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 87-90, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_23.pdf.

24

David Flores-Peñaloza and Francisco Javier Zaragoza Martinez.
Every four-colorable graph is isomorphic to a subgraph of the visibility graph of the integer lattice.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 91-94, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_24.pdf.

25

Fabrizio Frati.
Planar packing of diameter-four trees.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 95-98, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_25.pdf.

26

Zachary Abel, Brad Ballinger, Prosenjit Bose, S´ebastien Collette, Vida Dujmovic, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila P´or, and David R. Wood.
Every large point set contains many collinear points or an empty pentagon.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 99-102, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_26.pdf.

27

Erin W. Chambers and David Letscher.
On the height of a homotopy.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 103-106, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_27.pdf.

28

A. Maheshwari, J.-R. Sack, and K. Shahbaz.
Computing fr'echet distance with speed limits.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 107-110, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_28.pdf.

29

Mark orner, Jack Brimberg, Henrik Juel, and Anita Scobel.
General minisum circle location.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 111-114, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_29.pdf.

30

Joondong Kim, Joseph S.B. Mitchell, and Jingyu Zou.
Approximating maximum flow in polygonal domains using spanners.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 115-118, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_30.pdf.

31

Marc van Kreveld.
Bold graph drawings.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 119-122, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_31.pdf.

32

Vishal Verma and Jack Snoeyink.
Defining and computing accessibility radius.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 123-126, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_32.pdf.

33

Leonidas J. Guibas.
Intrinsic multiscale geometry.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), page 127, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_33.pdf.

34

Ananda Swarup Das, Prosenjit Gupta, and Kannan Srinathan.
Data structures for reporting extension violations in a query range.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 129-132, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_34.pdf.

35

Saladi Rahul, Prosenjit Gupta, and K. S. Rajan.
Data structures for range aggregation by categories.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 133-136, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_35.pdf.

36

Yoshio Okamoto and Ryuhei Uehara.
How to make a picturesque maze.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 137-140, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_36.pdf.

37

Minghui Jiang.
An inequality on the edge lengths of triangular meshes.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 141-144, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_37.pdf.

38

Erik D. Demaine, S´andor P. Fekete, G¨unter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke.
Integer point sets minimizing average pairwise ℓ1 distance: What is the optimal shape of a town?
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 145-148, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_38.pdf.

39

Tobias Christ and Michael Hoffmann.
Wireless localization with vertex guards is np-hard.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 149-152, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_39.pdf.

40

Evangelos Kranakis, Danny Krizanc, Lata Narayanan, and Kun Xu.
Inapproximability of the perimeter defense problem.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 153-156, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_40.pdf.

41

Jonathan Backer and J. Mark Keil.
The bichromatic rectangle problem in high dimensions.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 157-160, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_41.pdf.

42

Shiliang Cui, Iyad A. Kanj, and Ge Xia.
On the dilation of delaunay triangulations of points in convex position.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 161-164, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_42.pdf.

43

Prosenjit Bose, Luc Devroye, Maarten L"offler, Jack Snoeyink, and Vishal Verma.
The spanning ratio of the delaunay triangulation is greater than $pi/2$.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 165-167, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_43.pdf.

44

Prosenjit Bose, Jean Cardinal, Sebastien Collette, Erik D. Demaine, Belen Palop, Perouz Taslakian, and Norbert Zeh.
Relaxed gabriel graphs.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pages 169-172, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_44.pdf.

45

Raimund Seidel.
Teaching computational geometry, II.
In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), page 173, 2009.
URL http://cccg.ca/proceedings/2009/cccg09_45.pdf.
URL http://cccg.ca/proceedings/2009/cccg09_45_slides.pdf.gz.