Conference Program
All coffee breaks, technical sessions, and invited talks are accessed through the foyer of the Tory Building (labelled TB on the Campus Map).
| Sunday, August 19, 2007 | ||
| 17:00–20:00 | Welcome Reception | |
| Monday, August 20, 2007 | ||
| Session 1A | Session 1B | |
| 8:50–9:10 | Esther Arkin, Joseph Mitchell and Jack Snoeyink. Capturing Crossings: Convex Hulls of Segment and Plane Intersections | Eyal Ackerman, Oswin Aichholzer and Balázs Keszegh. Improved Upper Bounds on the Reflexivity of Point Sets |
| 9:10–9:30 | Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane Souvaine and Csaba Toth. Disjoint Segments Have Convex Partitions with 2-edge Connected | Boaz Ben-Moshe, Binay Bhattacharya, Sandip Das, Daya Gaur and Qiaosheng Shi. Computing a planar widest empty alpha-siphon in o(n^3) time |
| 9:30–9:50 | Ovidiu Daescu and Steven Bitner. Finding Segments and Triangles Spanned by Points in R^3 | Marc van Kreveld and Bettina Speckmann. On the number of empty pseudo-triangles in point sets |
| 9:50-10:10 | Coffee break | |
| 10:10-10:30 | Val Pinciu. On the Fewest Nets Problem for Convex Polyhedra | Stefan Naeher and Martin Taphorn. Experimental Evaluation of Structural Filtering as a Tool for Exact and Efficient Geometric Computing |
| 10:30-10:50 | Michael Langberg and Leonard J. Schulman. Contraction and Expansion of Convex Sets | Marc Mörig and Stefan Schirra. On the Design and Performance of Reliable Geometric Predicates using Error-free Transformations and Exact Sign of Sum Algorithms |
| 10:50-11:00 |
Break |
|
|
|
Session 2 (Invited talk) |
|
| 11:00-12:00 | Anna Lubiw. Morphing Planar Graph Drawings. | |
| 12:00–13:30 | Lunch break | |
| Session 3A | Session 3B | |
| 13:30–13:50 | Prosenjit Bose and Jason Morrison. Optimal Point Set Partitioning using Rigid Motion Star Placement | David Letscher. Reconstructing Submanifolds of Euclidean Space |
| 13:50–14:10 | Boaz Ben-Moshe and Yefim Dinitz. Fast Additive Constant Approximation Algorithms for the Safe Deposit Boxes Problem with Two and Three Currencies | Sheung-Hung Poon. On Unfolding Trees and Polygons on Various Lattices |
| 14:10–14:30 | Jonathan Lenchner. An Improved Bound for the Affine Sylvester Problem | Eric Sedgwick, Marcus Schaefer and Daniel Stefankovic. Spiralling and Folding: The Topological View |
| 14:30-14:50 | Asish Mukhopadhyay and Eugene Greene. The Ordinary Line Problem Revisited | Alex Benton and Joseph O'Rourke. Unfolding Polyhedra via Cut-Tree Truncation |
| 14:50–15:20 | Coffee break | |
| Session 4A | Session 4B | |
| 15:20–15:40 | Ovidiu Daescu and Steven Bitner. Minimum-sum Dipolar Spanning Tree for Points in R^3 | Matthew J. Katz, Nissan Lev-Tov and Gila Morgenstern. Conflict-Free Coloring of Points on a Line with respect to a Set of Intervals |
| 15:40–16:00 | Md. Kamrul Islam, Henk Meijer, Yurai Nüñez Rodríguez, David Rappaport and Henry Xiao. Hamilton Circuits in Hexagonal Grid Graphs | Balázs Keszegh. Weak Conflict-free Colorings of Point Sets and Simple Regions |
| 16:00–16:20 | Therese Biedl. Realizations of Hexagonal Graph Representations | Peter Brass, Ferran Hurtado, Benjamin Lafreniere and Anna Lubiw. A Lower Bound on the Area of a 3-Coloured Disc Packing |
| 16:30 | Open Problems Session | |
| Tuesday, August 21, 2007 | ||
| Session 5A | Session 5B | |
| 8:50–9:10 | Joachim Giesen, Balint Miklos and Mark Pauly. Medial Axis Approximation of Planar Shapes from Union of Balls: A Simpler and more Robust Algorithm | Boaz Ben-Moshe, Liad Serruya and Ariel Shamir. Image Compression Terrain Simplification |
| 9:10–9:30 | Martin Brooks and Liam Watson. Simplification of Scalar Data via Monotone-Light Factorizations | Boaz Ben-Moshe, Matthew Katz and Igor Zaslavsky. Distance Preserving Terrain Simplification - An Experimental Study |
| 9:30–9:50 | Audrey Lee, Ileana Streinu and Louis Theran. The slider-pinning problem | Suddha Basu and Jack Snoeyink. Terrain Representation using Right-Triangulated Irregular Networks |
| 9:50-10:10 | Coffee break | |
| 10:10-10:30 | Soeren Laue and Domagoj Matijevic. Approximating k-hop Minimum Spanning Trees in Euclidean Metrics | Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian and Godfried Toussaint. Vertex Pops and Popturns |
| 10:30-10:50 | Zhiyong Lin. Terminal Steiner Tree with Bounded Edge Length | Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sandor Fekete, Christian Knauer, André Schulz and Perouz Taslakian. On Rolling Cube Puzzles |
| 10:50-11:00 |
Break |
|
|
|
Session 6 (Invited talk) |
|
| 11:00-12:00 | Geza Tóth. Relationships between different crossing numbers of graphs. | |
| 12:00–13:30 | Lunch break | |
| Session 7A | Session 7B | |
| 13:30–13:50 | Binay Bhattacharya and Jeff Sember. Efficient Snap Rounding with Integer Arithmetic | Rodrigo Silveira and Marc van Kreveld. Towards a Definition of Higher Order Constrained Delaunay Triangulations |
| 13:50–14:10 | Eli Packer. Extending the Power of Snap Rounding Variants | David Letscher. Vector Weighted Anisotropic Voronoi Diagrams and Delaunay Traingulations |
| 14:10–14:30 | Peyman Afshani and Arash Farzan. Cache-Oblivious Output-Sensitive Two-Dimensional Convex Hull |
Priya Ranjan Sinha Mahapatra, Partha
P. Goswami and Sandip Das. Covering Points by Isothetic Unit
Squares
|
| 14:30-14:50 | Artur Czumaj, Gereon Frahling and Christian Sohler. Efficient Kinetic Data Structures for MaxCut | Trung Nguyen, Jean-Daniel Boissonnat, Frederic Falzon and Christian Knauer. A Disk-covering Problem with Application in Optical Interferometry |
| 14:50–15:20 | Coffee break | |
| Session 8A | Session 8B | |
| 15:20–15:40 | Zouhour Ben Azouz, Prosenjit Bose, Chang Shu and Stefanie Wuhrer. Approximations of Geodesic Distances for Incomplete Triangular Manifolds | Sasanka Roy, Sachin Lodha, Sandip Das and Anil Maheshwari. Approximate Shortest Descent Path on a Terrain |
| 15:40–16:00 | Dror Aiger and Klara Kedem. Exact and approximate Geometric Pattern Matching for point sets in the plane under similarity transformations | Ethan Kim, Sue Whitesides and Giuseppe Liotta. A Note on Drawing Direction-constrained Paths in 3D |
| 16:00–16:20 | Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid and Stefanie Wuhrer. Linear-Space Algorithms for Distance Preserving Embedding | Yury Kholondyrev and William Evans. Optimistic and Pessimistic Shortest Paths on Uncertain Terrains |
| 18:30 | Banquet - Chateau Laurier Hotel | |
| Wednesday, August 22, 2007 | ||
| Session 9A | Session 9B | |
| 8:50–9:10 | Cem Boyaci, Hale Erten and Alper Ungor. Triangulations Loosing Bundles and Weight | Shabnam Aziza and Therese Biedl. Improved Layouts of the Multigrid Network |
| 9:10–9:30 | Hale Erten and Alper Ungor. Computing Acute and Non-obtuse Triangulations | Fabrizio Frati. Straight-line Drawings of Outerplanar Graphs in O(dn log n) Area |
| 9:30–9:50 | Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl and Bettina Speckmann. On (Pointed) Minimum Weight Pseudo-Triangulations | Ethan Kim, Anil Ada, Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes, Samuli Heilala, Jonathan Li On Wing, Louis-Francois Preville-Ratelle, Sue Whitesides and Nuo Yu. On Bus Graph Realizability |
| 9:50-10:10 | Coffee break | |
| 10:10-10:30 | Boris Aronov, Marc van Kreveld, Maarten Löffler and Rodrigo Silveira. Largest Subsets of Triangles in a Triangulation | Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvil, Pietro Palladino, Maurizio Patrignani and Francesco Trotta. Homothetic Triangle Contact Representations of Planar Graphs |
| 10:30-10:50 | Moriguchi Masaki and Kokichi Sugihara. Restricted Edge Contractions in Triangulations of the Sphere with Boundary | Oswin Aichholzer, Günter Rote, André Schulz and Birgit Vogtenhuber. Pointed Drawings of Planar Graphs |
| 10:50-11:00 |
Break |
|
|
|
Session 10 (Invited talk) |
|
| 11:00-12:00 | Otfried Cheong. ”The Harmony of Spheres" | |
| 12:00–13:30 | Lunch break | |
| Session 11A | Session 11B | |
| 13:30–13:50 | Pengpeng Wang, Ramesh Krishnamurti and Kamal Gupta. Generalized Watchman Route Problem with Discrete View Cost | Teofilo Gonzalez and Arturo Gonzalez. Approximation Algorithms for the Minimum-Length Corridor and Related Problems |
| 13:50–14:10 | Stephen Bahun and Anna Lubiw. Optimal Schedules for 2-guard Room Search | Pierre Kraemer, David Cazier and Dominique Bechmann. A General and Efficient Representation for Multiresolution Meshes: Application to Quad/Triangle Subdivision |
| 14:10–14:30 | AmirAli Khosravi, Alireza Zarei and Mohammad Ghodsi. Efficient Visibility Maintenance of a Moving Segment Observer inside a Simple Polygon | Roman Rolinsky and François Dupret. Practical C1 Reparametrization of Piecewise Rational Bezier Curves |
| 14:30–14:50 | Coffee break | |
| Session 12 | ||
| 14:50–15:10 | Asish Mukhopadhyay and Eugene Greene. On a Geometric Approach to the Segment Sum Problem and its Generalization | |
| 15:10–15:30 | Amr Elmasry and Kazuhisa Makino. Finding Intersections of Bichromatic Segments Defined by Points | |
| 15:30–15:50 | Arindam Karmakar, Sasanka Roy and Sandip Das. Fast Computation of Smallest Enclosing Circle with Center on a Query Line Segment | |