This list is also available as a BibTeX file.

CCCG 2007 Papers

1

Anna Lubiw.
Morphing planar graph drawings.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), page 1, 2007.
URL http://cccg.ca/proceedings/2007/001.pdf.

2

Géza Tóth.
Note on the pair-crossing number and the odd-crossing number.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 3-6, 2007.
URL http://cccg.ca/proceedings/2007/002.pdf.

3

Otfried Cheong.
The harmony of spheres.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), page 7, 2007.
URL http://cccg.ca/proceedings/2007/003.pdf.

4

Esther M. Arkin, Joseph S. B. Mitchell, and Jack Snoeyink.
Capturing crossings: Convex hulls of segment and plane intersections.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 9-11, 2007.
URL http://cccg.ca/proceedings/2007/01a1.pdf.

5

Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
Disjoint segments have convex partitions with 2-edge connected dual graphs.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 13-16, 2007.
URL http://cccg.ca/proceedings/2007/01a2.pdf.
URL http://cccg.ca/proceedings/2007/01a2full.pdf.

6

Steven Bitner and Ovidiu Daescu.
Finding segments and triangles spanned by points in r$^{\mbox{3}}$.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 17-20, 2007.
URL http://cccg.ca/proceedings/2007/01a3.pdf.

7

Val Pinciu.
On the fewest nets problem for convex polyhedra.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 21-24, 2007.
URL http://cccg.ca/proceedings/2007/01a4.pdf.

8

Michael Langberg and Leonard J. Schulman.
Contraction and expansion of convex sets.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 25-28, 2007.
URL http://cccg.ca/proceedings/2007/01a5.pdf.
URL http://cccg.ca/proceedings/2007/01a5full.pdf.

9

Eyal Ackerman, Oswin Aichholzer, and Balázs Keszegh.
Improved upper bounds on the reflexivity of point sets.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 29-32, 2007.
URL http://cccg.ca/proceedings/2007/01b1.pdf.
URL http://cccg.ca/proceedings/2007/01b1full.pdf.

10

Boaz Ben-Moshe, Binay K. Bhattacharya, Sandip Das, Daya Ram Gaur, and Qiaosheng Shi.
Computing a planar widest empty alpha-siphon in o(n$^{\mbox{3}}$) time.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 33-36, 2007.
URL http://cccg.ca/proceedings/2007/01b2.pdf.
URL http://cccg.ca/proceedings/2007/01b2full.pdf.

11

Marc J. van Kreveld and Bettina Speckmann.
On the number of empty pseudo-triangles in point sets.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 37-40, 2007.
URL http://cccg.ca/proceedings/2007/01b3.pdf.

12

Stefan Näher and Martin Taphorn.
Experimental evaluation of structural filtering as a tool for exact and efficient geometric computing.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 41-44, 2007.
URL http://cccg.ca/proceedings/2007/01b4.pdf.
URL http://cccg.ca/proceedings/2007/01b4full.pdf.

13

Marc Mörig and Stefan Schirra.
On the design and performance of reliable geometric predicates using error-free transformations and exact sign of sum algorithms.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 45-48, 2007.
URL http://cccg.ca/proceedings/2007/01b5.pdf.
URL http://cccg.ca/proceedings/2007/01b5full.pdf.

14

Prosenjit Bose and Jason Morrison.
Optimal point set partitioning using rigid motion star placement.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 49-52, 2007.
URL http://cccg.ca/proceedings/2007/03a1.pdf.

15

Boaz Ben-Moshe and Yefim Dinitz.
Fast additive constant approximation algorithms for the safe deposit boxes problem with two and three currencies.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 53-56, 2007.
URL http://cccg.ca/proceedings/2007/03a2.pdf.
URL http://cccg.ca/proceedings/2007/03a2full.pdf.

16

Jonathan Lenchner.
An improved bound for the affine sylvester problem.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 57-60, 2007.
URL http://cccg.ca/proceedings/2007/03a3.pdf.

17

Asish Mukhopadhyay and Eugene Greene.
The ordinary line problem revisited.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 61-64, 2007.
URL http://cccg.ca/proceedings/2007/03a4.pdf.

18

David Letscher.
Reconstructing submanifolds of euclidean space.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 65-68, 2007.
URL http://cccg.ca/proceedings/2007/03b1.pdf.

19

Sheung-Hung Poon.
On unfolding trees and polygons on various lattices.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 69-72, 2007.
URL http://cccg.ca/proceedings/2007/03b2.pdf.
URL http://cccg.ca/proceedings/2007/03b2full.pdf.

20

Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic.
Spiralling and folding: The topological view.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 73-76, 2007.
URL http://cccg.ca/proceedings/2007/03b3.pdf.

21

Alex Benton and Joseph O'Rourke.
Unfolding polyhedra via cut-tree truncation.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 77-80, 2007.
URL http://cccg.ca/proceedings/2007/03b4.pdf.
URL http://cccg.ca/proceedings/2007/03b4full.pdf.

22

Steven Bitner and Ovidiu Daescu.
Minimum-sum dipolar spanning tree for points in r$^{\mbox{3}}$.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 81-84, 2007.
URL http://cccg.ca/proceedings/2007/04a1.pdf.

23

Kamrul Islam, Henk Meijer, Yurai Núñez Rodríguez, David Rappaport, and Henry Xiao.
Hamilton circuits in hexagonal grid graphs.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 85-88, 2007.
URL http://cccg.ca/proceedings/2007/04a2.pdf.

24

Therese C. Biedl.
Realizations of hexagonal graph representations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 89-92, 2007.
URL http://cccg.ca/proceedings/2007/04a3.pdf.

25

Matthew J. Katz, Nissan Lev-Tov, and Gila Morgenstern.
Conflict-free coloring of points on a line with respect to a set of intervals.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 93-96, 2007.
URL http://cccg.ca/proceedings/2007/04b1.pdf.

26

Balázs Keszegh.
Weak conflict-free colorings of point sets and simple regions.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 97-100, 2007.
URL http://cccg.ca/proceedings/2007/04b2.pdf.

27

Peter Brass, Ferran Hurtado, Benjamin J. Lafreniere, and Anna Lubiw.
A lower bound on the area of a 3-coloured disc packing.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 101-104, 2007.
URL http://cccg.ca/proceedings/2007/04b3.pdf.
URL http://cccg.ca/proceedings/2007/04b3full.pdf.

28

Joachim Giesen, Balint Miklos, and Mark Pauly.
Medial axis approximation of planar shapes from union of balls: A simpler and more robust algorithm.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 105-108, 2007.
URL http://cccg.ca/proceedings/2007/05a1.pdf.
URL http://cccg.ca/proceedings/2007/05a1full.pdf.

29

Martin Brooks and Liam Watson.
Simplification of scalar data via monotone-light factorizations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 109-112, 2007.
URL http://cccg.ca/proceedings/2007/05a2.pdf.

30

Audrey Lee, Ileana Streinu, and Louis Theran.
The slider-pinning problem.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 113-116, 2007.
URL http://cccg.ca/proceedings/2007/05a3.pdf.

31

Sören Laue and Domagoj Matijevic.
Approximating k-hop minimum spanning trees in euclidean metrics.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 117-120, 2007.
URL http://cccg.ca/proceedings/2007/05a4.pdf.
URL http://cccg.ca/proceedings/2007/05a4full.pdf.

32

Zhiyong Lin.
Terminal steiner tree with bounded edge length.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 121-123, 2007.
URL http://cccg.ca/proceedings/2007/05a5.pdf.
URL http://cccg.ca/proceedings/2007/05a5full.pdf.

33

Boaz Ben-Moshe, Liad Serruya, and Ariel Shamir.
Image compression terrain simplification.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 125-128, 2007.
URL http://cccg.ca/proceedings/2007/05b1.pdf.
URL http://cccg.ca/proceedings/2007/05b1full.pdf.

34

Boaz Ben-Moshe, Matthew J. Katz, and Igor Zaslavsky.
Distance preserving terrain simplification - an experimental study.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 129-132, 2007.
URL http://cccg.ca/proceedings/2007/05b2.pdf.
URL http://cccg.ca/proceedings/2007/05b2full.pdf.

35

Suddha Basu and Jack Snoeyink.
Terrain representation using right-triangulated irregular networks.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 133-136, 2007.
URL http://cccg.ca/proceedings/2007/05b3.pdf.

36

Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, and Godfried T. Toussaint.
Vertex pops and popturns.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 137-140, 2007.
URL http://cccg.ca/proceedings/2007/05b4.pdf.

37

Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sándor P. Fekete, Christian Knauer, André Schulz, and Perouz Taslakian.
On rolling cube puzzles.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 141-144, 2007.
URL http://cccg.ca/proceedings/2007/05b5.pdf.
URL http://cccg.ca/proceedings/2007/05b5full.pdf.

38

Binay K. Bhattacharya and Jeff Sember.
Efficient snap rounding with integer arithmetic.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 145-148, 2007.
URL http://cccg.ca/proceedings/2007/07a1.pdf.
URL http://cccg.ca/proceedings/2007/07a1full.pdf.

39

Eli Packer.
Extending the power of snap rounding variants.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 149-152, 2007.
URL http://cccg.ca/proceedings/2007/07a2.pdf.

40

Peyman Afshani and Arash Farzan.
Cache-oblivious output-sensitive two-dimensional convex hull.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 153-155, 2007.
URL http://cccg.ca/proceedings/2007/07a3.pdf.

41

Artur Czumaj, Gereon Frahling, and Christian Sohler.
Efficient kinetic data structures for maxcut.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 157-160, 2007.
URL http://cccg.ca/proceedings/2007/07a4.pdf.

42

Rodrigo I. Silveira and Marc J. van Kreveld.
Towards a definition of higher order constrained delaunay triangulations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 161-164, 2007.
URL http://cccg.ca/proceedings/2007/07b1.pdf.

43

David Letscher.
Vector weighted anisotropic voronoi diagrams and delaunay traingulations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 165-168, 2007.
URL http://cccg.ca/proceedings/2007/07b2.pdf.

44

Priya Ranjan Sinha Mahapatra, Partha P. Goswami, and Sandip Das.
Covering points by isothetic unit squares.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 169-172, 2007.
URL http://cccg.ca/proceedings/2007/07b3.pdf.

45

Trung Nguyen, Jean-Daniel Boissonnat, Frédéric Falzon, and Christian Knauer.
A disk-covering problem with application in optical interferometry.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 173-176, 2007.
URL http://cccg.ca/proceedings/2007/07b4.pdf.
URL http://cccg.ca/proceedings/2007/07b4full.pdf.

46

Zouhour Ben Azouz, Prosenjit Bose, Chang Shu, and Stefanie Wuhrer.
Approximations of geodesic distances for incomplete triangular manifolds.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 177-180, 2007.
URL http://cccg.ca/proceedings/2007/08a2.pdf.
URL http://cccg.ca/proceedings/2007/08a2full.pdf.

47

Dror Aiger and Klara Kedem.
Exact and approximate geometric pattern matching for point sets in the plane under similarity transformations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 181-184, 2007.
URL http://cccg.ca/proceedings/2007/08a2.pdf.
URL http://cccg.ca/proceedings/2007/08a2full.pdf.

48

Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel H. M. Smid, and Stefanie Wuhrer.
Linear-space algorithms for distance preserving embedding.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 185-188, 2007.
URL http://cccg.ca/proceedings/2007/08a3.pdf.

49

Sasanka Roy, Sachin Lodha, Sandip Das, and Anil Maheshwari.
Approximate shortest descent path on a terrain.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 189-192, 2007.
URL http://cccg.ca/proceedings/2007/08b1.pdf.
URL http://cccg.ca/proceedings/2007/08b1full.pdf.

50

Ethan Kim, Sue Whitesides, and Giuseppe Liotta.
A note on drawing direction-constrained paths in 3d.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 193-196, 2007.
URL http://cccg.ca/proceedings/2007/08b2.pdf.

51

Yury Kholondyrev and William Evans.
Optimistic and pessimistic shortest paths on uncertain terrains.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 197-200, 2007.
URL http://cccg.ca/proceedings/2007/08b3.pdf.

52

Cem Boyaci, Hale Erten, and Alper Üngör.
Triangulations loosing bundles and weight.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 201-204, 2007.
URL http://cccg.ca/proceedings/2007/09a1.pdf.
URL http://cccg.ca/proceedings/2007/09a1full.pdf.

53

Hale Erten and Alper Üngör.
Computing acute and non-obtuse triangulations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 205-208, 2007.
URL http://cccg.ca/proceedings/2007/09a2.pdf.

54

Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, and Bettina Speckmann.
On (pointed) minimum weight pseudo-triangulations.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 209-212, 2007.
URL http://cccg.ca/proceedings/2007/09a3.pdf.

55

Boris Aronov, Marc J. van Kreveld, Maarten Löffler, and Rodrigo I. Silveira.
Largest subsets of triangles in a triangulation.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 213-216, 2007.
URL http://cccg.ca/proceedings/2007/09a4.pdf.

56

Masaki Moriguchi and Kokichi Sugihara.
Restricted edge contractions in triangulations of the sphere with boundary.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 217-220, 2007.
URL http://cccg.ca/proceedings/2007/09a5.pdf.

57

Shabnam Aziza and Therese C. Biedl.
Improved layouts of the multigrid network.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 221-224, 2007.
URL http://cccg.ca/proceedings/2007/09b1.pdf.

58

Fabrizio Frati.
Straight-line drawings of outerplanar graphs in o(dn log n) area.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 225-228, 2007.
URL http://cccg.ca/proceedings/2007/09b2.pdf.
URL http://cccg.ca/proceedings/2007/09b2full.pdf.

59

Anil Ada, Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes, Samuli Heilala, Ethan Kim, Jonathan Li On Wing, Louis-Francois Preville-Ratelle, Sue Whitesides, and Nuo Yu.
On bus graph realizability.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 229-232, 2007.
URL http://cccg.ca/proceedings/2007/09b3.pdf.

60

Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvíl, Pietro Palladino, Maurizio Patrignani, and Francesco Trotta.
Homothetic triangle contact representations of planar graphs.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 233-236, 2007.
URL http://cccg.ca/proceedings/2007/09b4.pdf.
URL http://cccg.ca/proceedings/2007/09b4full.pdf.

61

Oswin Aichholzer, Günter Rote, André Schulz, and Birgit Vogtenhuber.
Pointed drawings of planar graphs.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 237-240, 2007.
URL http://cccg.ca/proceedings/2007/09b5.pdf.

62

Pengpeng Wang, Ramesh Krishnamurti, and Kamal Gupta.
Generalized watchman route problem with discrete view cost.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 241-244, 2007.
URL http://cccg.ca/proceedings/2007/11a1.pdf.
URL http://cccg.ca/proceedings/2007/11a1full.pdf.

63

Stephen Bahun and Anna Lubiw.
Optimal schedules for 2-guard room search.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 245-248, 2007.
URL http://cccg.ca/proceedings/2007/11a2.pdf.
URL http://cccg.ca/proceedings/2007/11a2full.pdf.

64

AmirAli Khosravi, Alireza Zarei, and Mohammad Ghodsi.
Efficient visibility maintenance of a moving segment observer inside a simple polygon.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 249-252, 2007.
URL http://cccg.ca/proceedings/2007/11a3.pdf.

65

Arturo Gonzalez-Gutierrez and Teofilo F. Gonzalez.
Approximation algorithms for the minimum-length corridor and related problems.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 253-256, 2007.
URL http://cccg.ca/proceedings/2007/11b1.pdf.

66

Pierre Kraemer, David Cazier, and Dominique Bechmann.
A general and efficient representation for multiresolution meshes: Application to quad/triangle subdivision.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 257-260, 2007.
URL http://cccg.ca/proceedings/2007/11b2.pdf.

67

Roman Rolinsky and François Dupret.
Practical c$^{\mbox{1}}$ reparametrization of piecewise rational bézier curves.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 261-264, 2007.
URL http://cccg.ca/proceedings/2007/11b3.pdf.

68

Asish Mukhopadhyay and Eugene Greene.
On a geometric approach to the segment sum problem and its generalization.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 265-268, 2007.
URL http://cccg.ca/proceedings/2007/12a1.pdf.
URL http://cccg.ca/proceedings/2007/12a1full.pdf.

69

Amr Elmasry and Kazuhisa Makino.
Finding intersections of bichromatic segments defined by points.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 269-272, 2007.
URL http://cccg.ca/proceedings/2007/12a2.pdf.

70

Arindam Karmakar, Sasanka Roy, and Sandip Das.
Fast computation of smallest enclosing circle with center on a query line segment.
In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG2007), pages 273-276, 2007.
URL http://cccg.ca/proceedings/2007/12a3.pdf.