CCCG 2010: 22nd Canadian Conference on Computational Geometry  -  August 9-11, 2010  -  University of Manitoba, Winnipeg, Canada
Click here for a printable version of the conference program or in a single-page pamphlet format.
There are two parallel tracks for contributed talks. 17 minutes are allocated for each presentation and 3 minutes for questions and the transition to the next talk.
There will be coffee breaks from 10:40-11:00 and 2:50-3:10 each day. Lunch will be from 12:00-1:30.
Sunday, August 8  
Welcome Reception (EITC E2-229)
6:00 Reception and Registration
Monday, August 9  
Conference Opening (EITC E2-105)
9:00 David Barnard, President of the University of Manitoba Welcome and Opening Address
1A Covering and Guarding (EITC E2-105) 1B Proximity Graphs (EITC E2-165)
9:40 Fajie Li and Reinhard Klette Watchman Route in a Simple Polygon with a Rubberband Algorithm Prosenjit Bose, Sebastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, Vera Sacristan and Maria Saumell Some Properties of Higher Order Delaunay and Gabriel Graphs
10:00 Zohreh Jabbari, William Evans and David Kirkpatrick Multi-guard Covers for Polygonal Regions Eva Kopecka, Daniel Reem and Simeon Reich Existence of Zone Diagrams in Compact Subsets of Uniformly Convex Spaces
10:20 Giovanni Viglietta and Maurizio Monge The 3-dimensional Searchlight Scheduling Problem Birgit Vogtenhuber, Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Alexander Pilz, Pedro Ramos and Marc van Kreveld Blocking Delaunay Triangulations
Paul Erdős Memorial Lecture (EITC E2-105)
11:00 David Avis Those Ubiquitous Cut Polyhedra
2A Geometric Sensor Networks (EITC E2-105) 2B Kinetic and Dynamic Data (EITC E2-165)
1:30 Leonidas Guibas, Nikola Milosavljevic and Arik Motskin Connected Dominating Sets on Dynamic Geometric Graphs Zahed Rahmati and Alireza Zarei Combinatorial Changes of Euclidean Minimum Spanning Tree of Moving Points in the Plane
1:50 Paz Carmi and Lilach Chaitman Stable Roommates and Geometric Spanners Marek Sulovsky and Uli Wagner k-Sets and Continuous Motion in R3
2:10 Alaa Eddien Abdallah, Thomas Fevens and Jaroslav Opatrny 3D Local Algorithm for Dominating Sets of Unit Disk Graphs Ebrahim Ehsanfar, Bahram Sadeghi Bigham and Najmeh Madadi An Optimal Solution for Dynamic Polar Diagram
2:30 Boaz Ben-Moshe, Paz Carmi, Lilach Chaitman, Matthew Katz, Gila Morgenstern and Yael Stein Direction Assignment in Wireless Networks Thuy Le and Bradford Nickerson Towards a Dynamic Data Structure for Efficient Bounded Line Range Search
3A Degeneracy of Point Sets (EITC E2-105) 3B Graph Colouring (EITC E2-165)
3:10 Kimikazu Kato On Degeneracy of a Lower Envelope of Algebraic Surfaces Radoslav Fulek Coloring Geometric Hypergraph Defined by an Arrangement of Half-Planes
3:30 David Charlton, Erik Demaine, Martin Demaine, Vida Dujmovic, Pat Morin and Ryuhei Uehara Ghost Chimneys Minghui Jiang, Vincent Pilaud and Pedro Tejada On a Dispersion Problem in Grid Labeling
3:50 Perouz Taslakian and Isabel Hubard Deflating Polygons to the Limit Kyle Klein and Subhash Suri Robot Kabaddi
Open Problem Session (EITC E2-105)
4:20 Erik Demaine and Joseph O'Rourke Open Problem Session
Tuesday, August 10        
4A Triangulations and Polyhedralizations (EITC E2-105) 4B Scheduling and Partitioning (EITC E2-165)
9:00 Kimikazu Kato On Degeneracy of a Lower Envelope of Algebraic Surfaces David Millman, Matthew O'Meara, Jack Snoeyink and Vishal Verma Maximum Geodesic Flow in the Plane with Obstacles
9:20 Birgit Vogtenhuber, Thomas Hackl and Oswin Aichholzer Compatible Pointed Pseudo-Triangulations Braxton Carrigan Evading Equilateral Triangles without a Map
9:40 Luca Castelli Aleardi, Eric Fusy and Thomas Lewiner Optimal Encoding of Triangular and Quadrangular Meshes with Fixed Topology Adrian Dumitrescu and Csaba Toth Watchman Tours for Polygons with Holes
10:00 Gill Barequet, Nadia Benbernou, David Charlton, Erik Demaine, Martin Demaine, Mashhood Ishaque, Anna Lubiw, Andre Schulz, Diane Souvaine, Godfried Toussaint and Andrew Winslow Bounded-Degree Polyhedronization of Point Sets Hoda Akbari and Mohammad Ghodsi Visibility Maintenance of a Moving Segment Observer inside Polygons with Holes
10:20 Jorge Urrutia, Canek Pelaez and Adriana Ramirez-Vigueras Triangulations with Many Points of Even Degree Craig Dillabaugh I/O Efficient Path Traversal in Well-Shaped Tetrahedral Meshes
Invited Lecture (EITC E2-105)
11:00 David Eppstein Regular Labelings and Geometric Structures
5A Discrete Mathematics (EITC E2-105) 5B Medians and Epsilon-nets (EITC E2-165)
1:30 Adrian Dumitrescu Approximate Euclidean Ramsey Theorems Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman and Pat Morin Oja Medians and Centers of Gravity
1:50 Ana Paula Malheiro and Jorge Stolfi Finding Minimal Bases in Arbitrary Spline Spaces Riddhipratim Basu, Bhaswar Bhattacharya and Tanmoy Talukdar The Projection Median of a Set of Points in R^d
2:10 Erik Demaine, Martin Demaine and Ryuhei Uehara Any Monotone Function Can Be Realized by Interlocked Polygons Pradeesha Ashok, Sathish Govindarajan and Janardhan Kulkarni Small Strong Epsilon Nets
2:30 Hiroyuki Miyata, Sonoko Moriyama and Komei Fukuda Complete Enumeration of Small Realizable Oriented Matroids Janardhan Kulkarni and Sathish Govindarajan New Epsilon-Net Constructions
6A Enclosings (EITC E2-105) 6B Polygonal Distance Metrics (EITC E2-165)
3:10 Prosenjit Bose, Otfried Cheong and Vida Dujmovic On the Perimeter of Fat Objects Xiuxia Pan, Fajie Li and Reinhard Klette Approximate Shortest Path Algorithms for Sequences of Pairwise Disjoint Simple Polygons
3:30 Yonit Bousany, Mary Leah Karker, Joseph O'Rourke and Leona Sparaco Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup Anil Maheshwari, Jorg-Rudiger Sack, Kaveh Shahbaz and Hamid Zarrabi-Zadeh Speed-Constrained Geodesic Fréchet Distance Inside a Simple Polygon
3:50 Prosenjit Bose and Jean-Lou De Carufel Minimum Enclosing Area Triangle with a Fixed Angle Robert Fraser and Patrick K. Nicholson Hausdorff Core of a One Reflex Vertex Polygon
Business Meeting (EITC E2-105)
4:20 CCCG Organizing Committee Business Meeting: All conference attendees are invited.
Conference Banquet (Inn at the Forks)
6:00 Bus departs from the University of Manitoba for the Forks
6:30 Conference Banquet at the Inn at the Forks
Wednesday, August 11      
7A Graph Algorithms and Graph Drawing (EITC E2-105) 7B Polygons and Folding (EITC E2-165)
9:00 Stefan Huber and Martin Held Computing Straight Skeletons of Planar Straight-Line Graphs Based on Motorcycle Graphs Gautam Das, Asish Mukhopadhyay, Subhas C. Nandy, Sangameswar Patil and S. V. Rao Computing the Straight Skeleton of a Monotone Polygon in O(n log n) Time
9:20 Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman and Jawaherul Alam Minimum-Area Drawings of Plane 3-Trees William Steiger and Imre Barany On the Variance of Random Polygons
9:40 Dhia Mahjoub, Angelika Leskovskaya and David Matula Approximating the Independent Domatic Partition Problem in Random Geometric Graphs - An Experimental Study Jeff Sember and William Evans k-Star-Shaped Polygons
10:00 Maryam Tahmasbi and S. Mehdi Hashemi Orthogonal thickness of graphs Anna Lubiw, Erik Demaine, Martin Demaine, Arlo Shallit and Jonah Shallit Zipper Unfoldings of Polyhedral Complexes
10:20 Maarten Loffler and Martin Nollenburg Shooting Bricks with Orthogonal Laser Beams: A First Step towards Internal/External Map Labeling Ryuhei Uehara On Stretch Minimization Problem on Unit Strip Paper
Invited Lecture (EITC E2-105)
11:00 David Kirkpatrick Determining the Robustness of Sensor Barriers
8A Facility Location (EITC E2-105) 8B Range Searching (EITC E2-165)
1:30 Md. Shafiul Alam and Asish Mukhopadhyay A New Algorithm and Improved Lower Bound for Point Placement on a Line in Two Rounds Gautam Das and Bradford Nickerson I/O-Efficient Triangular Range Search and its Application
1:50 Adrian Dumitrescu and Minghui Jiang Constrained k-Center and Movement to Independence Saladi Rahul, Haritha Bellam, Prosenjit Gupta and Krishnan Rajan Range Aggregate Structures for Colored Geometric Objects
2:10 Fatemeh Panahi and Ali Mohades Computing Minimum Limited-Capacity Matching in one-Dimensional space and for the Points Lying on Two Perpendicular Lines Yakov Nekrich and Michiel Smid Approximating Range-Aggregate Queries using Coresets
2:30 Bhaswar Bhattacharya and Subhas C. Nandy New Variations of the Reverse Facility Location Problem
9A Optimization (EITC E2-105) 9B Ham Sandwich Problems (EITC E2-165)
3:10 Adrian Dumitrescu The Traveling Salesman Problem for Lines and Rays in the Plane Farnaz Sheikhi, Mark de Berg, Ali Mohades and Mansoor Davoodi Monfared Finding Monochromatic L-Shapes in Bichromatic Point Sets
3:30 Prosenjit Bose, Karim Douieb, Vida Dujmovic, John Howat and Pat Morin Fast Local Searches and Updates in Bounded Universes Radoslav Fulek, Balazs Keszegh, Filip Moric and Igor Uljarevic On Polygons Excluding Point Sets
3:50 Sanjib Sadhu, Arijit Bishnu, Subhas C. Nandy and Partha P. Goswami Cluster Connecting Problem inside a Polygon William Steiger, Mario Szegedy and Jihui Zhao Six-Way Equipartitioning by Three Lines in the Plane