The 14th Canadian Conference on Computational Geometry
August 12-14, 2002

View Web Friendly Version

Conference Program

Monday August 12

Time L1050 L1060
8:45-9:00   Opening Remarks
  1A Chair: Henk Meijer 1B Chair: Mark Keil
9:00-9:30 Proximate Point Searching
Erik D. Demaine, John Iacono, Stefan Langerman
On the Hardness of Turn-Angle-Restricted Rectilinear Cycle Cover Problems
Steph Durocher, David Kirkpatrick
9:30-10:00 Point Location Algorithms of Minimum Size
Valentina Damerow, Lukas Finschi, Martin Ziegler
Ordered Theta Graphs
Prosenjit Bose, Joachim Gudmundsson, Pat Morin
10:00-10:30 Using Simplicial Partitions to Determine a Closest Point to a Query Line
Asish Mukhopadhyay
Logarithmic Path-Length in Space-Filling Curves
Jens-Michael Wierum
10:30-11:00 Coffee
11:00-12:00   Invited Talk: Luc Devroye (introduced by: Jit Bose)
12:00-1:30 Lunch
  2A Chair: Hazel Everett 2B Chair: Tom Shermer
1:30-2:00 On Flat-State Connectivity of Chains with Fixed Acute Angles
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint
Hierarchical Planar Voronoi Diagram Approximations
I. Boada, N. Coll, J. A. Sellares
2:00-2:30 PUSH-2-F is PSPACE-Complete
Erik D. Demaine, Robert A. Hearn, Michael Hoffman
The Complexity of Flow Diagrams in the Plane
Joachim Giesen, Matthias John
2:30-3:00 Constructing Convex 3-Polytopes from Two Triangulations of a Polygon
Benjamin Marlin, Godfried Toussaint
Constructing Differentiable Homeomorphisms Between Isomorphic Triangulations
Frederick Crimins, Diane Souvaine
3:00-3:30 Coffee
  3A Chair: Sylvain Lazard 3B Chair: Therese Biedl
3:30-4:00 Efficient Answering of Polyhedral Queries in Rd Using BBS-Trees
K. Elbassioni, A. Elmasry, I. Kamel
Connecting Points in the Presence of Obstacles in the Plane
Michael Hoffman, Csaba D. Toth
4:00-4:30 Analysis of Half-Space Range Search Using the k-d Search Skip List
Mario A. Lopez, Bradford G. Nickerson
Computing Signed Permutations of Polygons
Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
4:30-5:30 Open Problems - chair: Joseph O'Rourke

Tuesday August 13

Time L1050 L1060
  4A Chair: 4B Chair: Mark Keil
9:00-9:30 An Exact Algebraic Predicate for Maintaining the Topology of the Voronoi Diagram for Circles
Francois Anton, David Kirkpatrick, Darka Mioc
Partitioning a Deformed Urban Grid
Leonard Hagger, Ian Sanders
9:30-10:00 Robust Algorithm for k-Gon Voronoi Diagram Construction
Zhenming Chen, Evanthia Papadopoulou, Jinhui Xu
Exact and Approximation Algorithms for Computing a-fat Decompositions
Mirela Damian-Iordache
10:00-10:30 A Reliable Algorithm for Computing the Generalized Voronoi Diagram for a Set of Spheres in the Euclidean d-dimensional Space
M. L. Gavrilova
Partitioning Orthogonal Polygons into Fat Rectangles in Polynomial Time
Joseph O'Rourke, Geetika Tewari
10:30-11:00 Coffee
11:00-12:00   Invited Talk: Ulrich Kortenkamp
12:00-1:00 Lunch
  5A Chair: Alex Lopez-Ortiz 5B Chair: Godfried Toussaint
1:00-1:30 Nonorthogonal Polyhedra Built from Rectangles
Melody Donoso, Joseph O'Rourke
Computing Closest Points for Segments
Sergei Bespamyatnikh
1:30-2:00 Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, Ming-wei Wang
A Sweep Line Algorithm for Nearest Neighbour Queries
Joao Dinis, Margarida Mamede
2:00-2:30 Cost-Optimal Quadtrees for Ray Shooting
Herve Bronnimann, Marc Glisse, David R. Wood
On Reverse Nearest Neighbour Queries
Anil Maheshwari, Jan Vahrenhold, Norbert Zeh
2:30-3:00 On the Number of Lines Tangent to Four Convex Polyhedra
H. Bronnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, S. Whitesides
A Near-Quadratic Algorithm for the Alpha-Connected Two-Center Decision Problem
P. H. Huang, Y. T. Tsai, C. Y. Tang
3:00-4:30 Travel to Waterton
5:30-6:30 Boat Cruise
7:00-9:00 Supper and Business Meeting
9:00-10:30 Return from Waterton

Wednesday August 14

Time L1050 L1060
9:00-10:00 Invited Talk: Stan Wagon
10:00-10:30 Coffee
  6A Chair: Hazel Everett 6B Chair:
10:30-11:00 Convexity Minimizes Pseudo-Triangulations
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann
Searching for the Center of a Circle
T. Biedl, M. Hasan, J. D. Horton, A. Lopez-Ortiz, T. Vinar
11:00-11:30 Enumerating Pseudo-Triangulations in the Plane
Sergei Bespamyatnikh
Light Edges in Degree-Constrained Graphs
Prosenjit Bose, Michiel Smid, David R. Wood
11:30-12:00 Asymptotically Efficient Triangulations of the d-cube
David Orden, Francisco Santos
Drawing K2,n: A Lower Bound
Therese Biedl, Timothy M. Chan, Alejandro Lopez-Ortiz
12:00-12:30 On Sampling and Reconstructing Surfaces with Boundaries
M. Gopi
Drawing Series-Parallel Graphs on a Box
Emilio Di Giacomo, Giuseppe Liotta, Stephen K. Wismath
12:30-1:00   A Linear Algorithm for Compact Box-Drawings of Trees
Masud Hasan, Md. Saidur Rahman, Takao Nishizeki

Last modified: 06/28/2002