CCCG 2008 Program

Room A is McConnell 204.
Room B is McConnell 302.

Tuesday August 12, 2008
18:00-22:00 Thomson House Welcome reception and registration.
Wednesday August 13, 2008
8:40-9:10 Room A Registration (registration desk will be open until noon).
9:10-9:30 Room A Introduction and Opening Remarks
Session 1A (Pat Morin)
9:30-9:50 Room A Ravi Janardan, Prosenjit Gupta, Yokesh Kumar and Michiel Smid.
Data Structures for Range-Aggregate Extent Queries
9:50-10:10 Room A Marek Karpinski and Yakov Nekrich.
Searching for Frequent Colors in Rectangles
10:10-10:30 Room A Mashhood Ishaque, Diane Souvaine and Nadia Benbernou.
Data Structures for Restricted Triangular Range Searching
Session 1B (Perouz Taslakian)
9:30-9:50 Room B Gerhard Guettler and Colin Mallows.
A generalization of Apollonian packing of circles
9:50-10:10 Room B Svetlana Stolpner, Jonathan Lenchner, Giuseppe Liotta, David Bremner, Christophe Paul, Marc Pouget and Stephen Wismath.
A note on alpha-drawable k-trees
10:10-10:30 Room B James King.
VC-Dimension of Visibility on Terrains
10:30-11:00   Coffee break
Session 2A (Stefan Langerman)
11:00-11:20 Room A Ryuhei Uehara.
Polygons Folding to Plural Incongruent Orthogonal Boxes
11:20-11:40 Room A Alex Benton and Joseph O'Rourke.
A Class of Convex Polyhedra with Few Edge Unfoldings
11:40-12:00 Room A Youichi Fujimoto, Mitsuo Motoki and Ryuhei Uehara.
Inverting Linkages with Stretch
Session 2B (Michiel Smid)
11:00-11:20 Room B Deepanjan Kesh and Shashank Mehta.
Polynomial irreducibility testing through Minkowski summand computation
11:20-11:40 Room B Jérémy Barbay and Eric Y, Chen.
Convex Hull of the Union of Convex Objects in the Plane: an Adaptive Analysis
11:40-12:00 Room B Mojtaba Nouri Bygi and Mohammad Ghodsi.
Polar Diagram of Moving Objects
12:00-13:30   Lunch (on your own)
Session 3 (David Avis)
13:30-14:30 Room A Paul Erdos Memorial Lecture: Ron Graham.
Iterated Partitions of Triangles
14:30-15:00   Coffee break
Session 4A (Jason Morrison)
15:00-15:20 Room A Prosenjit Bose, Joseph O'Rourke, Chang Shu and Stefanie Wuhrer.
Isometric Morphing of Triangular Meshes
15:20-15:40 Room A Christian Wulff-Nilsen.
Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics
15:40-16:00 Room A Manjish Pal.
The Focus of Attention Problem Revisited
Session 4B (Will Evans)
15:00-15:20 Room B Adrian Dumitrescu.
On distinct distances among points in general position and other related problems
15:20-15:40 Room B Adrian Dumitrescu and Minghui Jiang.
Monochromatic simplices of any volume
15:40-16:00 Room B Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Clemens Huemer and Jorge Urrutia.
Empty Monochromatic Triangles
16:00-16:30   Coffee break
Session 5A (Stefanie Wuhrer)
16:30-16:50 Room A Greg Aloupis, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman and Joseph O'Rourke.
Draining a Polygon--or--Rolling a Ball out of a Polygon
16:50-17:10 Room A Eric McCreath.
Partial Matching of Planar Polygons Under Translation and Rotation
17:10-17:30 Room A Subhas Nandy, Krishnendu Mukhopadhyaya and Bhargab B. Bhattacharya.
Recognition of Largest Empty Orthoconvex Polygon in a Point Set
Session 5B (Mohammad Farshi)
16:30-16:50 Room B Natasa Jovanovic, Jan Korst and Augustus J.E.M. Janssen.
Minimum blocking sets of circles for a set of lines in the plane
16:50:17:10 Room B Mohammad Ali Abam, Mark de Berg and Sheung-Hung Poon.
Fault-Tolerant Conflict-Free Coloring
17:10-17:30 Room B Joseph O'Rourke, Perouz Taslakian and Godfried Toussaint.
A Pumping Lemma for Homometric Rhythms
Thursday August 14, 2008
Session 6A (Pat Morin)
9:00-9:10 Room A Registration (registration desk will be open until noon).
9:10-9:30 Room A Priya Ranjan Sinha Mahapatra, Partha P. Goswami and Sandip Das.
Maximal Covering by Two Isothetic Unit Squares
9:30-9:50 Room A Greg Aloupis, Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman and Bettina Speckmann.
Triangulating and Guarding Realistic Polygons
9:50-10:10 Room A Marcus Schaefer, Eric Sedgwick and Daniel Stefankovic.
Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time
10:10-10:30 Room A Benoît Hudson and Duru Türkoglu.
An Efficient Query Structure for Mesh Refinement
Session 6B (Paz Carmi)
9:10-9:30 Room B Qiaosheng Shi and Binay Bhattacharya.
Application of computational geometry to network p-center location problems
9:30-9:50 Room B Jihui Zhao and William Steiger.
Generalized Ham-Sandwich Cuts for Well Separated Point Sets
9:50-10:10 Room B Selim Akl, Kamrul Islam and Henk Meijer.
Direct Planar Tree Transformation and Counterexample
10:10-10:30 Room B Dania El-Khechen, John Iacono, Thomas Fevens and Günter Rote.
Partitioning a Polygon into Two Mirror Congruent Pieces
10:30-11:00   Coffee break
Session 7A (Mirela Damian)
11:00-11:20 Room A Esther Arkin, George Hart, Joondong Kim, Irina Kostitsyna, Joseph Mitchell, Girishkumar Sabhnani and Steven Skiena.
The Embroidery Problem
11:20-11:40 Room A Erik D. Demaine, Martin L. Demaine and Vi Hart.
Computational Balloon Twisting: The Theory of Balloon Polyhedra
11:40-12:00 Room A Henk Meijer, Yurai Núñez Rodríguez and David Rappaport.
On the Complexity of Point Recolouring in Geometric Graphs
Session 7B (Steven Wismath)
11:00-11:20 Room B Karim Abu Affash and Matthew J.Katz.
Improved Bounds on the Average Distance to the Fermat-Weber Center of a Convex Object
11:20-11:40 Room B Mohammad Moharrami and Avner Magen.
On the nonexistence of dimension reduction for $\ell2_2$ metrics
11:40-12:00 Room B Mina Razaghpour and Anna Lubiw.
The Steiner Ratio for Obstacle-Avoiding Rectilinear Steiner Trees
12:00-13:30   Lunch (on your own)
Session 8 (Joseph O'Rourke)
13:30-14:30 Room A Invited Talk: Michael Shamos.
How Did It Start?
14:30-15:00   Coffee break
Session 9A (Dana Jansens)
15:00-15:20 Room A Hamid Zarrabi-Zadeh.
Core-Preserving Algorithms
15:20-15:40 Room A Jonathan Derryberry, Don Sheehy, Maverick Woo and Danny Sleator.
Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors
15:40-16:00 Room A Prosenjit Bose, Stefan Langerman and Sasanka Roy.
Smallest enclosing circle centered on a query line segment
Session 9B (Karim Douieb)
15:00-15:20 Room B Khaled Elbassioni and Hans Raj Tiwary.
On a Cone Covering Problem
15:20-15:40 Room B Don Sheehy, Gary Miller and Todd Phillips.
Linear-Size Meshes
15:40-16:00 Room B Hamid Reza Chitsaz, Steven M. LaValle and Jason O'Kane.
Exact Pareto-Optimal Coordination of Two Translating Polygonal Robots on a Cyclic Roadmap
16:00-16:30   Coffee break
Session 10 (Erik Demaine and Joseph O'Rourke)
16:20-17:30 Room A Open problems session and business meeting
18:30-23:00 Thomson House Banquet and live music from the Algorhythmics
Friday August 15, 2008
Session 11A (Pat Morin)
9:00-9:10 Room A Registration (registration desk will be open until noon).
9:10-9:30 Room A Ovidiu Daescu and Anastasia Kurdia.
Polygonal Chain Simplification with Small Angle Constraints
9:30-9:50 Room A Maia Fraser, Evangelos Kranakis and Jorge Urrutia.
Memory Requirements for Local Geometric Routing and Traversal in Digraphs
9:50-10:10 Room A Yurai Núñez Rodríguez, Henry Xiao, Kamrul Islam and Waleed Alsalih.
A Distributed Algorithm for Computing Voronoi Diagram in the Unit Disk Graph Model
10:10-10:30 Room A Stefan Naeher and Daniel Schmitt.
A Framework for Multi-Core Implementations of Divide and Conquer Algorithms and its Application to the Convex Hull Problem
Session 11B (Sebastien Collette)
9:10-9:30 Room B Jeff Sember and William Evans.
Guaranteed Voronoi Diagrams of Uncertain Sites
9:30-9:50 Room B Joachim Giesen, Madhusudan Manjunath and Michael Eigensatz.
The Solution Path of the Slab Support Vector Machine
9:50-10:10 Room B Reza Dorrigiv and Alejandro Lopez-Ortiz.
Adaptive Searching in One and Two Dimensions
10:10-10:30 Room B Peter Damaschke.
Competitive Search for Longest Empty Intervals
10:30-11:00   Coffee break
Session 12 (Godfried Toussaint)
11:00-12:00 Room A Invited Talk: Dmitri Tymoczko.
The Geometry of Music
12:00-12:05 Room A Closing remarks and farewell