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