The 19th Canadian Conference on Computational Geometry
August 20-22, 2007

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


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


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


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