Preliminary Program


Accepted Papers

Mon August 11

Tue August 12
Wed August 13
Fees and Registration
Travel Information

There will be an informal reception for all CCCG participants on Sunday evening between 7pm and 9pm. The reception will be in the atrium of the computer science building on the Dalhousie University campus (6050 University Avenue). Participants will be able to pick up their conference registration and proceedings at the reception.

Monday, August 11
8:15-8:45Coffee, registration open
9:00-10:00Paul Erdos Memorial Lecture
Ferran Hurtado
Coffee and snacks
10:30-11:00 A Combinatorial Maximum Cover Approach to 2D Translational Geometric Covering
Karen Daniels, Arti Mathur, and Roger Grinde

Planar case of the maximum box and related problems
Ying Liu and Mikhail Nediak

11:00-11:30 On the parameterized complexity of a generalized Rush Hour puzzle
Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar Ragde, and Klaus Reinhardt

Estimation of the necessary number of points in Riemannian Voronoi diagram
Kensuke Onishi and Jin-ichi Itoh

11:30-12:00 Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard
Tetsuo Asano, David Kirkpatrick, and Chee Yap
An Implementation of a linear time algorithm for computing the minimum perimeter triangle enclosing a convex polygon
Anna Medvedeva and Asish Mukhopadhyay

13:30-14:00 Parallel Morphing of Trees and Cycles
Therese Biedl, Anna Lubiw, and Michael Spriggs

Partitioning Regular Polygons into Circular Pieces I: Convex Partitions
Mirela Damian and Joseph O'Rourke

14:00-14:30 The spanning ratios of Beta-Skeleton
Weizhao Wang, Xiang-Yang Li, Yu Wang, and Wen-Zhan Song

Equiprojective Polyhedra
Masud Hasan and Anna Lubiw

14:30-15:00 Approximating the Geometric Minimum-Diameter Spanning Tree
Michael Spriggs, Mark Keil, Sergei Bespamyatnikh, Michael Segal, and Jack Snoeyink

On the worst-case complexity of the silhouette of a polytope
Helmut Alt, Marc Glisse, and Xavier Goaoc

Coffee and snacks
15:30-16:00 Coloring Objects Built From Bricks
Suzanne Gallagher and Joseph O'Rourke

Linear Binary Space Partitions and Hierarchy of Object Classes
Petr Tobola and Karel Nechvile

16:00-16:30 Encoding Quadrilateral Meshes
Asish Mukhopadhyay and Quanbin Jing

A Space-Efficient Algorithm for Segment Intersection
Eric Chen and Timothy Chan

Open problem session

Tuesday, August 12
8:30-9:00Coffee, registration open
9:00-10:00Invited Presentation
Algorithmic Approaches to Digital Halftoning
Tetsuo Asano
Coffee and snacks
10:30-11:00 Curves of Width One and the River Shore Problem
Timothy M. Chan, Alexander Golynski, Alejandro Lopez-Ortiz, and Claude-Guy Quimper

Molecular graphs of a finite points set : a generalization of the Delaunay triangulation
Melkemi Mahmoud

11:00-11:30 Triangle Guarding
Jocelyn Smith and William Evans

The Strange Complexity of Constrained Delaunay Triangulation
Nicolas Grislain and Jonathan Shewchuk

11:30-12:00 Computing the Similarity of two Melodies
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, David Rappaport, and Godfried Toussaint

Computing Delaunay Triangulation with Imprecise Input Data
Ali Khanban and Abbas Edalat

13:30-14:00 Hinged Dissection of Polygons is Hard
Robert Hearn, Erik Demaine, and Greg Frederickson

On Coherent Rotation Angles for As-Rigid-As-Possible Shape Interpolation
Jaeil Choi and Andrzej Szymczak

14:00-14:30 Decomposing Polygons Into Diameter Bounded Components
Chris Worman

A Genetic Algorithm for the Minimum Tetrahedralization of a Convex Polyhedron
Ian Hsieh, Kiat-Choong Chen, and Cao An Wang

14:30-15:00 On Polyhedra Induced by Point Sets in Space
Ferran Hurtado, Godfried Toussaint, and Joan Trias

Sufficiently Fat Polyhedra are Not 2-Castable
Alexander Golynski and David Bremner

Coffee and snacks
15:30-16:00 The Gaussian Centre of a Set of Mobile Points
Steph Durocher and David Kirkpatrick

Computing a closest point to a circular ring
Pinaki Mitra, Asish Mukhopadhyay, and S.Veerabhadreshawra Rao

16:00-16:30 Network Design Subject to Facility Location
Laxmi Gewali, Joy Bhadury, and Ramaswamy Chandrasekaran

On Exact Solution for a Point-Location Problem in a System of d-dimensional Hyperbolic Surfaces
Sergei Bespamyatnikh and Marina Gavrilova

Halifax Citadel
19:00Conference Supper and Business Meeting

Wednesday, August 13
8:30-9:00Coffee, registration open
9:00-10:00Invited Presentation
On the Efficiency of Bounding-Volume Hierarchies
Mark de Berg
Coffee and snacks
10:30-11:00 On the Number of Pseudo-Triangulations of Certain Point Sets
Oswin Aichholzer, David Orden, Francisco Santos, and Bettina Speckmann

On the Complexity of Halfspace Volume Queries
Erik D. Demaine, Jeff Erickson, and Stefan Langerman

11:00-11:30 An Algorithm for the MaxMin Area Triangulation of a Convex Polygon
J. Mark Keil and Tzvetalin Vassilev

Multidimensional Orthogonal Range Search Using Tries
Lingke Bu and Bradford Nickerson

11:30-12:00 A Constant Approximation Algorithm for Maximum Weight Triangulation
Shiyan Hu

Shortest Paths in Two Intersecting Pencils of Lines
David Hart

12:00-12:30 Degree Bounds for Constrained Pseudo-Triangulations
Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, and Csaba David Tóth

On Shortest Paths in Line Arrangements
T. Kavitha and Kasturi Varadarajan

12:30-13:00   On the number of transversals to line segments in R^3
Herve Brönnimann, Hazel Everett, Sylvain Lazard, Frank Sottile, and Sue Whitesides

Conference closing
  18-Jul-2003 /