This list is also available as a BibTeX file.

CCCG 2010 Papers

1

Fajie Li and Reinhard Klette.
Watchman route in a simple polygon with a rubberband algorithm.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 1-4, 2010.
URL http://cccg.ca/proceedings/2010/paper03.pdf.

2

Zohreh Jabbari, William Evans, and David Kirkpatrick.
Multi-guard covers for polygonal regions.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 5-8, 2010.
URL http://cccg.ca/proceedings/2010/paper04.pdf.

3

Giovanni Viglietta and Maurizio Monge.
The 3-dimensional searchlight scheduling problem.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 9-12, 2010.
URL http://cccg.ca/proceedings/2010/paper05.pdf.

4

Prosenjit Bose, Sébastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, Vera Sacristan, and Maria Saumell.
Some properties of higher order delaunay and gabriel graphs.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 13-16, 2010.
URL http://cccg.ca/proceedings/2010/paper06.pdf.

5

Eva Kopecka, Daniel Reem, and Simeon Reich.
Existence of zone diagrams in compact subsets of uniformly convex spaces.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 17-20, 2010.
URL http://cccg.ca/proceedings/2010/paper07.pdf.

6

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Alexander Pilz, Pedro Ramos, Marc van Kreveld, and Birgit Vogtenhuber.
Blocking delaunay triangulations.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 21-24, 2010.
URL http://cccg.ca/proceedings/2010/paper08.pdf.

7

David Avis.
Those ubiquitous cut polyhedra.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), page 25, 2010.
URL http://cccg.ca/proceedings/2010/paper09.pdf.

8

Leonidas Guibas, Nikola Milosavljevic, and Arik Motskin.
Connected dominating sets on dynamic geometric graphs.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 27-30, 2010.
URL http://cccg.ca/proceedings/2010/paper10.pdf.

9

Paz Carmi and Lilach Chaitman.
Stable roommates and geometric spanners.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 31-34, 2010.
URL http://cccg.ca/proceedings/2010/paper11.pdf.

10

Alaa Eddien Abdallah, Thomas Fevens, and Jaroslav Opatrny.
3d local algorithm for dominating sets of unit disk graphs.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 35-38, 2010.
URL http://cccg.ca/proceedings/2010/paper12.pdf.

11

Boaz Ben-Moshe, Paz Carmi, Lilach Chaitman, Matthew Katz, Gila Morgenstern, and Yael Stein.
Direction assignment in wireless networks.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 39-42, 2010.
URL http://cccg.ca/proceedings/2010/paper13.pdf.

12

Zahed Rahmati and Alireza Zarei.
Combinatorial changes of euclidean minimum spanning tree of moving points in the plane.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 43-45, 2010.
URL http://cccg.ca/proceedings/2010/paper14.pdf.

13

Marek Sulovsky and Uli Wagner.
$k$-sets and continuous motion in $\mathbb{R}^3$.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 47-50, 2010.
URL http://cccg.ca/proceedings/2010/paper15.pdf.

14

Ebrahim Ehsanfar, Bahram Sadeghi Bigham, and Najmeh Madadi.
An optimal solution for dynamic polar diagram.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 51-54, 2010.
URL http://cccg.ca/proceedings/2010/paper16.pdf.

15

Thuy Le and Bradford Nickerson.
Towards a dynamic data structure for efficient bounded line range search.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 55-58, 2010.
URL http://cccg.ca/proceedings/2010/paper17.pdf.

16

Kimikazu Kato.
On degeneracy of lower envelopes of algebraic surfaces.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 59-62, 2010.
URL http://cccg.ca/proceedings/2010/paper18.pdf.

17

David Charlton, Erik Demaine, Martin Demaine, Vida Dujmovic, Pat Morin, and Ryuhei Uehara.
Ghost chimneys.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 63-66, 2010.
URL http://cccg.ca/proceedings/2010/paper19.pdf.

18

Perouz Taslakian and Isabel Hubard.
Deflating polygons to the limit.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 67-70, 2010.
URL http://cccg.ca/proceedings/2010/paper20.pdf.

19

Radoslav Fulek.
Coloring geometric hypergraph defined by an arrangement of half-planes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 71-74, 2010.
URL http://cccg.ca/proceedings/2010/paper21.pdf.

20

Minghui Jiang, Vincent Pilaud, and Pedro Tejada.
On a dispersion problem in grid labeling.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 75-78, 2010.
URL http://cccg.ca/proceedings/2010/paper22.pdf.

21

Kyle Klein and Subhash Suri.
Robot kabaddi.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 79-82, 2010.
URL http://cccg.ca/proceedings/2010/paper23.pdf.

22

Erik Demaine and Joseph O'Rourke.
Open problem session.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 83-86, 2010.
URL http://cccg.ca/proceedings/2010/paper24.pdf.

23

Thomas Hackl, Oswin Aichholzer, and Birgit Vogtenhuber.
Compatible pointed pseudo-triangulations.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 91-94, 2010.
URL http://cccg.ca/proceedings/2010/paper26.pdf.

24

Luca Castelli Aleardi, Eric Fusy, and Thomas Lewiner.
Optimal encoding of triangular and quadrangular meshes with fixed topology.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 95-98, 2010.
URL http://cccg.ca/proceedings/2010/paper27.pdf.

25

Gill Barequet, Nadia Benbernou, David Charlton, Erik Demaine, Martin Demaine, Mashhood Ishaque, Anna Lubiw, Andre Schulz, Diane Souvaine, Godfried Toussaint, and Andrew Winslow.
Bounded-degree polyhedronization of point sets.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 99-102, 2010.
URL http://cccg.ca/proceedings/2010/paper28.pdf.

26

Jorge Urrutia, Canek Peláez, and Adriana Ramírez-Vigueras.
Triangulations with many points of even degree.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 103-106, 2010.
URL http://cccg.ca/proceedings/2010/paper29.pdf.

27

David Millman, Matthew O'Meara, Jack Snoeyink, and Vishal Verma.
Maximum geodesic routing in the plane with obstacles.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 107-108, 2010.
URL http://cccg.ca/proceedings/2010/paper30.pdf.

28

Braxton Carrigan.
Evading equilateral triangles without a map.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 109-112, 2010.
URL http://cccg.ca/proceedings/2010/paper31.pdf.

29

Adrian Dumitrescu and Csaba Toth.
Watchman tours for polygons with holes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 113-116, 2010.
URL http://cccg.ca/proceedings/2010/paper32.pdf.

30

Hoda Akbari and Mohammad Ghodsi.
Visibility maintenance of a moving segment observer inside polygons with holes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 117-120, 2010.
URL http://cccg.ca/proceedings/2010/paper33.pdf.

31

Craig Dillabaugh.
I/O efficient path traversal in well-shaped tetrahedral meshes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 121-124, 2010.
URL http://cccg.ca/proceedings/2010/paper34.pdf.

32

David Eppstein.
Regular labelings and geometric structures.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 125-130, 2010.
URL http://cccg.ca/proceedings/2010/paper35.pdf.

33

Adrian Dumitrescu.
Approximate euclidean ramsey theorems.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 131-134, 2010.
URL http://cccg.ca/proceedings/2010/paper36.pdf.

34

Ana Paula Malheiro and Jorge Stolfi.
Finding minimal bases in arbitrary spline spaces.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 135-138, 2010.
URL http://cccg.ca/proceedings/2010/paper37.pdf.

35

Erik Demaine, Martin Demaine, and Ryuhei Uehara.
Any monotone boolean function can be realized by interlocked polygons.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 139-142, 2010.
URL http://cccg.ca/proceedings/2010/paper38.pdf.

36

Hiroyuki Miyata, Sonoko Moriyama, and Komei Fukuda.
Complete enumeration of small realizable oriented matroids.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 143-146, 2010.
URL http://cccg.ca/proceedings/2010/paper39.pdf.

37

Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman, and Pat Morin.
Oja medians and centers of gravity.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 147-150, 2010.
URL http://cccg.ca/proceedings/2010/paper40.pdf.

38

Riddhipratim Basu, Bhaswar Bhattacharya, and Tanmoy Talukdar.
The projection median of a set of points in $\mathbb{R}^d$.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 151-154, 2010.
URL http://cccg.ca/proceedings/2010/paper41.pdf.

39

Pradeesha Ashok, Sathish Govindarajan, and Janardhan Kulkarni.
Small strong epsilon nets.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 155-158, 2010.
URL http://cccg.ca/proceedings/2010/paper42.pdf.

40

Janardhan Kulkarni and Sathish Govindarajan.
New $\epsilon$-net constructions.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 159-162, 2010.
URL http://cccg.ca/proceedings/2010/paper43.pdf.

41

Prosenjit Bose, Otfried Cheong, and Vida Dujmovic.
On the perimeter of fat objects.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 163-166, 2010.
URL http://cccg.ca/proceedings/2010/paper44.pdf.

42

Yonit Bousany, Mary Leah Karker, Joseph O'Rourke, and Leona Sparaco.
Sweeping minimum perimeter enclosing parallelograms: Optimal crumb cleanup.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 167-170, 2010.
URL http://cccg.ca/proceedings/2010/paper45.pdf.

43

Prosenjit Bose and Jean-Lou De Carufel.
Minimum enclosing area triangle with a fixed angle.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 171-174, 2010.
URL http://cccg.ca/proceedings/2010/paper46.pdf.

44

Xiuxia Pan, Fajie Li, and Reinhard Klette.
Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 175-178, 2010.
URL http://cccg.ca/proceedings/2010/paper47.pdf.

45

Anil Maheshwari, Jorg-Rudiger Sack, Kaveh Shahbaz, and Hamid Zarrabi-Zadeh.
Speed-constrained geodesic fréchet distance inside a simple polygon.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 179-182, 2010.
URL http://cccg.ca/proceedings/2010/paper48.pdf.

46

Robert Fraser and Patrick K. Nicholson.
Hausdorff core of a one reflex vertex polygon.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 183-186, 2010.
URL http://cccg.ca/proceedings/2010/paper49.pdf.

47

Stefan Huber and Martin Held.
Computing straight skeletons of planar straight-line graphs based on motorcycle graphs.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 187-190, 2010.
URL http://cccg.ca/proceedings/2010/paper50.pdf.

48

Debajyoti Mondal, Rahnuma Islam Nishat, Md.Saidur Rahman, and Jawaherul Alam.
Minimum-area drawings of plane 3-trees.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 191-194, 2010.
URL http://cccg.ca/proceedings/2010/paper51.pdf.

49

Dhia Mahjoub, Angelika Leskovskaya, and David Matula.
Approximating the independent domatic partition problem in random geometric graphs - an experimental study.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 195-198, 2010.
URL http://cccg.ca/proceedings/2010/paper52.pdf.

50

Maryam Tahmasbi and S.Mehdi Hashemi.
Orthogonal thickness of graphs.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 199-202, 2010.
URL http://cccg.ca/proceedings/2010/paper53.pdf.

51

Maarten Löffler and Martin Nöllenburg.
Shooting bricks with orthogonal laser beams: A first step towards internal/external map labeling.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 203-206, 2010.
URL http://cccg.ca/proceedings/2010/paper54.pdf.

52

Gautam Das, Asish Mukhopadhyay, Subhas C. Nandy, Sangameswar Patil, and S.V. Rao.
Computing the straight skeleton of a monotone polygon in $O(n \log n)$ time.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 207-210, 2010.
URL http://cccg.ca/proceedings/2010/paper55.pdf.

53

William Steiger and Imre Barany.
On the variance of random polygons.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 211-214, 2010.
URL http://cccg.ca/proceedings/2010/paper56.pdf.

54

Jeff Sember and William Evans.
$k$-star-shaped polygons.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 215-218, 2010.
URL http://cccg.ca/proceedings/2010/paper57.pdf.

55

Anna Lubiw, Erik Demaine, Martin Demaine, Arlo Shallit, and Jonah Shallit.
Zipper unfoldings of polyhedral complexes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 219-222, 2010.
URL http://cccg.ca/proceedings/2010/paper58.pdf.

56

Ryuhei Uehara.
On stretch minimization problem on unit strip paper.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 223-226, 2010.
URL http://cccg.ca/proceedings/2010/paper59.pdf.

57

David Kirkpatrick.
Determining the robustness of sensor barriers.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), page 227, 2010.
URL http://cccg.ca/proceedings/2010/paper60.pdf.

58

Md.Shafiul Alam and Asish Mukhopadhyay.
A new algorithm and improved lower bound for point placement on a line in two rounds.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 229-232, 2010.
URL http://cccg.ca/proceedings/2010/paper61.pdf.

59

Adrian Dumitrescu and Minghui Jiang.
Constrained $k$-center and movement to independence.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 233-236, 2010.
URL http://cccg.ca/proceedings/2010/paper62.pdf.

60

Fatemeh Panahi and Ali Mohades.
Computing minimum limited-capacity matching in one-dimensional space and for the points lying on two perpendicular lines.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 237-240, 2010.
URL http://cccg.ca/proceedings/2010/paper63.pdf.

61

Bhaswar B. Bhattacharya and Subhas C. Nandy.
New variations of the reverse facility location problem.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 241-244, 2010.
URL http://cccg.ca/proceedings/2010/paper64.pdf.

62

Gautam Das and Bradford Nickerson.
I/o-efficient triangular range search and its application.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 245-248, 2010.
URL http://cccg.ca/proceedings/2010/paper65.pdf.

63

Saladi Rahul, Haritha Bellam, Prosenjit Gupta, and Krishnan Rajan.
Range aggregate structures for colored geometric objects.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 249-252, 2010.
URL http://cccg.ca/proceedings/2010/paper66.pdf.

64

Yakov Nekrich and Michiel Smid.
Approximating range-aggregate queries using coresets.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 253-256, 2010.
URL http://cccg.ca/proceedings/2010/paper67.pdf.

65

Adrian Dumitrescu.
The traveling salesman problem for lines and rays in the plane.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 257-260, 2010.
URL http://cccg.ca/proceedings/2010/paper68.pdf.

66

Prosenjit Bose, Karim Douïeb, Vida Dujmovic, John Howat, and Pat Morin.
Fast local searches and updates in bounded universes.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 261-264, 2010.
URL http://cccg.ca/proceedings/2010/paper69.pdf.

67

Sanjib Sadhu, Arijit Bishnu, Subhas C. Nandy, and Partha P. Goswami.
Cluster connecting problem inside a polygon.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 265-268, 2010.
URL http://cccg.ca/proceedings/2010/paper70.pdf.

68

Farnaz Sheikhi, Mark de Berg, Ali Mohades, and Mansoor Davoodi Monfared.
Finding monochromatic l-shapes in bichromatic point sets.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 269-272, 2010.
URL http://cccg.ca/proceedings/2010/paper71.pdf.

69

Radoslav Fulek, Balázs Keszegh, Filip Moric, and Igor Uljarevic.
On polygons excluding point sets.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 273-276, 2010.
URL http://cccg.ca/proceedings/2010/paper72.pdf.

70

William Steiger, Mario Szegedy, and Jihui Zhao.
Six-way equipartitioning by three lines in the plane.
In Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pages 277-280, 2010.
URL http://cccg.ca/proceedings/2010/paper73.pdf.