18th Canadian Conference on Computational Geometry

August 14-16, 2006
Queen's University

Call for Papers
Accepted Papers
CCCG 06 Latex Style File

Fees and Registration

Travel Information


Conference Map

Program Schedule
There will be an informal reception for all CCCG participants on Sunday August 13 from 19:00 - 21:00 at Legett Hall (58 on the map above). Participants will be able to pick up their conference registration and proceedings at the reception.

The Conference technical sessions will be held in Dupuis Hall (19) Rooms 215 (A sessions) and 217 (B and plenary sessions). A registration desk will also be open every day in Dupuis Hall. The Conference Banquet on Tuesday August 15 18:30-23:00 will take place at Ban Righ Hall (71).
Monday, August 14
8:30 Early Morning Coffee
8:50 Welcome
9:00-10:00 Paul Erdős Memorial Lecture
Linkage Folding: From Erdős to Proteins
Erik Demaine



  Session 1A: Session 1B:
10:30-10:50 The complexity of a Pop-up book
Ryuhei Uehara and Sachio Teramoto
An Improved Approximation Factor For The Unit Disk Covering Problem
Sada Narayanappa and Petr Vojtechovsky

10:50-11:10 A Study of Conway's Thrackle Conjecture
Wei Li, Karen Daniels and Konstantin Rybnikov
Experimental Comparison of the Cost of Approximate and Exact Convex Hull Computation in the Plane
Jan Tusch and Stefan Schirra
11:10-11:30 Curves in the Sand: Algorithmic Drawing
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Dania El-Khechen, Robin Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane L. Souvaine, Perouz Taslakian and Godfried T. Toussaint
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
Stefan Funke, Theocharis Malamatos, Domagoj Matijevic and Nicola Wolpert




  Session 2A: Session 2B:
13:30-13:50 On Planar path transformation
Md. Kamrul Islam, Selim G. Akl and Henk Meijer

Realization of Degree 10 Minimum Spanning Trees in 3-Space
James King

13:50-14:10 Bounded-Curvature Path Normalization
Jonathan Backer and David Kirkpatrick

Predicates for Line Transversals in 3D
Hazel Everett, Sylvain Lazard, William Lenhart, Jeremy Redburn and Linqiao Zhang

14:10-14:30 Shortest Descending Paths through Given Faces
Mustaq Ahmed and Anna Lubiw

Small Weak Epsilon-Nets in Three Dimensions
Maryam Babazadeh and Hamid Zarrabi-Zadeh




  Session 3A: Session 3B:
15:00-15:20 Two-Guard Art Gallery Problem
Junqiang Zhou and Simeon Ntafos

Hamiltonian Cycles in Triangular Grids
Valentin Polishchuk, Esther Arkin and Joseph Mitchell

15:20-15:40 An Optimal Solution to Room Search Problem
Binay Bhattacharya, John Z. Zhang, Qiaosheng Shi and Tsunehiko Kameda

Tight Bounds for Point Recolouring
Yurai Núñez and David Rappaport

15:40-16:00 On computing shortest external watchman routes for convex polygons
Rafa Absar and Sue Whitesides
2D Triangulation Representation Using Stable Catalogs
Abdelkrim Mebarki, Luca Castelli Aleardi and Olivier Devillers


Open problem session


Tuesday, August 15
8:30 Early Morning Coffee
  Session 4A: Session 4B:
9:00-9:20 Polygon Reconstruction from Line Cross-Sections
Gill Barequet, Craig Gotsman and Avishay Sidlesky
On the Maximum Span of Fixed-Angle Chains
Nadia Benbernou and Joseph O'Rourke

9:20-9:40 Computing the Tool Path of an Externally Monotone Polygon in Linear Time
Prosenjit Bose, David Bremner and Diane L. Souvaine

Local Overlaps In Special Unfoldings Of Convex Polyhedra
Brendan Lucier
9:40-10:00 Optimal Polygon Placement
Prosenjit Bose and Jason Morrison
Spanning trees across axis-parallel segments
Csaba Tóth and Michael Hoffmann




  Session 5A: Session 5B:
10:30-10:50 Rotationally Monotone Polygons
Prosenjit Bose, Pat Morin, Michiel Smid and Stefanie Wuhrer

Routing with Guaranteed Delivery on Virtual Coordinates
Mirela Ben-Chen, Craig Gotsman and Steven Gortler

10:50-11:10 Polygons Flip Finitely: Flaws and a Fix
Erik D. Demaine, Blaise Gassend, Joseph O'Rourke and Godfried T. Toussaint

Practical and efficient geometric epsilon-approximations
Huseyin Akcan, Hervé Brönnimann and Robert Marini

11:10-11:30 Characterization of Polygons Searchable by a Boundary 1-Searcher
Tsunehiko Kameda, John Z. Zhang and Masafumi Yamashita

Geometric Separator for d-dimensional ball graphs
Kebin Wang and Shang-Hua Teng




13:30-14:30 Invited Lecture
On Approximate Range Searching
- or -
Get in Shape; Round is a Good Choice
David Mount



  Session 6A: Session 6B:
15:00-15:20 On the Smallest Enclosing Information Disk
Frank Nielsen and Richard Nock

The PKD-tree for orthogonal d-dimensional range search
Bradford Nickerson and Qingxiu Shi

15:20-15:40 Removing Outliers to Minimize Area and Perimeter
Rossen Atanassov, Pat Morin and Stefanie Wuhrer

Range-Aggregate Proximity Detection for Design Rule Checking in VLSI Layouts
R. Sharathkumar and Prosenjit Gupta

15:40-16:00 A Simple Streaming Algorithm for Minimum Enclosing Balls
Hamid Zarrabi-Zadeh and Timothy Chan


K-Nearest Neighbor Search using the Pyramid Technique
Bradford Nickerson and Qingxiu Shi
16:00-16:20 On Bipartite Matching under the RMS Distance
Jeff M. Phillips and Pankaj K. Agarwal
A Linear Space Data Structure for Orthogonal Range Reportingæand Emptiness Queries
Yakov Nekrich


Conference Banquet in Ban Righ Hall


Wednesday, August 16
8:30 Early Morning Coffee
9:00-10:00 Invited Lecture
Predicting the Flexibility and Rigidity of Proteins:
Geometry, Combinatorics, Conjectures, and Algorithms
Walter Whitely



  Session 7A: Session 7B:
10:30-10:50 Computational Euclid
Maarten van Emden and Belaid Moa
Computing Depth Contours with Graphics Hardware
Craig Gotsman and Ian Fischer

10:50-11:10 Another Paradigm for Geometric Constraints Solving
Dominique Michelucci, Sebti Foufou, Loic Lamarque and David Menegaux


Minimizing the Number of Arcs Linking a Permutation of Points in the Plane
Stephane Durocher, Chris Gray and James King
11:10-11:30 Partitioning a regular n-gon into n+1 convex congruent pieces is impossible, for sufficiently large n
Dania El-Khechen, Thomas Fevens and John Iacono
An O(n log n) algorithm for the all-farthest-segments problem for a planar set of points
Asish Mukhopadhyay and R.L. Scot Drysdale




1-April-2006 / cccg [at] cs [dot] queensu [dot] ca

Supported by: