




Time  Room L1050  Room L1060 

8:459:00  Opening Remarks  
1A Chair: Henk Meijer  1B Chair: Mark Keil  
9:009:30 
Proximate Point Searching Erik D. Demaine, John Iacono, Stefan Langerman 
On the Hardness of TurnAngleRestricted Rectilinear Cycle Cover Problems Steph Durocher, David Kirkpatrick 
9:3010:00 
Point Location Algorithms of Minimum Size Valentina Damerow, Lukas Finschi, Martin Ziegler 
Ordered Theta Graphs Prosenjit Bose, Joachim Gudmundsson, Pat Morin 
10:0010:30 
Using Simplicial Partitions to Determine a Closest Point to a Query Line Asish Mukhopadhyay 
Logarithmic PathLength in SpaceFilling Curves JensMichael Wierum 
10:3011:00  Coffee  
11:0012:00  Invited Talk: Luc Devroye (introduced by: Jit Bose)  
12:001:30  Lunch  
2A Chair: Hazel Everett  2B Chair: Tom Shermer  
1:302:00 
On FlatState 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:002:30 
PUSH2F is PSPACEComplete Erik D. Demaine, Robert A. Hearn, Michael Hoffman 
The Complexity of Flow Diagrams in the Plane Joachim Giesen, Matthias John 
2:303:00 
Constructing Convex 3Polytopes from Two Triangulations of a Polygon Benjamin Marlin, Godfried Toussaint 
Constructing Differentiable Homeomorphisms Between Isomorphic Triangulations Frederick Crimins, Diane Souvaine 
3:003:30  Coffee  
3A Chair: Sylvain Lazard  3B Chair: Therese Biedl  
3:304:00 
Efficient Answering of Polyhedral Queries in R^{d}
Using BBSTrees K. Elbassioni, A. Elmasry, I. Kamel 
Connecting Points in the Presence of Obstacles in the Plane Michael Hoffman, Csaba D. Toth 
4:004:30 
Analysis of HalfSpace Range Search Using the kd 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:305:30  Open Problems  Chair: Joseph O'Rourke 
Time  Room L1050  Room L1060 

4A Chair:  4B Chair: Mark Keil  
9:009: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:3010:00 
Robust Algorithm for kGon Voronoi Diagram Construction Zhenming Chen, Evanthia Papadopoulou, Jinhui Xu 
Exact and Approximation Algorithms for Computing afat Decompositions Mirela DamianIordache 
10:0010:30 
A Reliable Algorithm for Computing the Generalized Voronoi
Diagram for a Set of Spheres in the Euclidean ddimensional Space M. L. Gavrilova 
Partitioning Orthogonal Polygons into Fat Rectangles in Polynomial Time Joseph O'Rourke, Geetika Tewari 
10:3011:00  Coffee  
11:0012:00  Invited Talk: Ulrich Kortenkamp  
12:001:00  Lunch  
5A Chair: Alex LopezOrtiz  5B Chair: Godfried Toussaint  
1:001:30 
Nonorthogonal Polyhedra Built from Rectangles Melody Donoso, Joseph O'Rourke 
Computing Closest Points for Segments Sergei Bespamyatnikh 
1:302: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, Mingwei Wang 
A Sweep Line Algorithm for Nearest Neighbour Queries Joao Dinis, Margarida Mamede 
2:002:30 
CostOptimal Quadtrees for Ray Shooting Herve Bronnimann, Marc Glisse, David R. Wood 
On Reverse Nearest Neighbour Queries Anil Maheshwari, Jan Vahrenhold, Norbert Zeh 
2:303: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 NearQuadratic Algorithm for the AlphaConnected
TwoCenter Decision Problem P. H. Huang, Y. T. Tsai, C. Y. Tang 
3:004:30  Travel to Waterton  
5:306:30  Boat Cruise  
7:009:00  Supper and Business Meeting  
9:0010:30  Return from Waterton 
Time  Room L1050  Room L1060  

9:0010:00  Invited Talk: Stan Wagon  
10:0010:30  Coffee  
6A Chair: Hazel Everett  6B Chair:  
10:3011:00 
Convexity Minimizes PseudoTriangulations Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann 
Searching for the Center of a Circle T. Biedl, M. Hasan, J. D. Horton, A. LopezOrtiz, T. Vinar 

11:0011:30 
Enumerating PseudoTriangulations in the Plane Sergei Bespamyatnikh 
Light Edges in DegreeConstrained Graphs Prosenjit Bose, Michiel Smid, David R. Wood 

11:3012:00 
Asymptotically Efficient Triangulations of the dcube David Orden, Francisco Santos 
Drawing K_{2,n}: A Lower Bound Therese Biedl, Timothy M. Chan, Alejandro LopezOrtiz 

12:0012:30 
On Sampling and Reconstructing Surfaces with Boundaries M. Gopi 
Drawing SeriesParallel Graphs on a Box Emilio Di Giacomo, Giuseppe Liotta, Stephen K. Wismath 

12:301:00  A Linear Algorithm for Compact BoxDrawings of Trees Masud Hasan, Md. Saidur Rahman, Takao Nishizeki 