18th Canadian Conference on Computational Geometry

August 14-16, 2006
Queen's University


Home
Call for Papers
Submission
Accepted Papers
CCCG 06 Latex Style File
Program

Fees and Registration

Accommodation
Travel Information
Kingston

Contact

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

10:00-10:30

Coffee-break


  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

 

11:30-13:30

Lunch-break


  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

 

14:30-15:00

Coffee-break


  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
 

16:15-17:15

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

 

10:00-10:30

Coffee-break


  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

 

11:30-13:30

Lunch-break


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

14:30-15:00

Coffee-break


  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
 

18:30

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

10:00-10:30

Coffee-break


  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

 

11:40

Goodbye

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

Supported by: