Lethbridge Lethbridge
|
|
|
|
|
| Time | Room L1050 | Room 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 | |
| Time | Room L1050 | Room 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 | |
| Time | Room L1050 | Room 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 |
||