 |
|
All technical sessions will be held in the Leacock Building.
|
|
|
| |||
| Welcoming reception at Thomson House. | 18:00- 23:00 | ||
|
| |||
|
Leacock Room 26 Chair: Luc Devroye | |||
| Paul Erdös Lecture The Erdös-Szekeres Theorem -- 65 Years Later János Pach, Hungarian Academy of Sciences |
09:00 |
||
|
| |||
| Coffee break | 10:00 | ||
|
| |||
|
Leacock Room 26 Session 1A Chair: Francisco Gómez | Leacock Room 219 Session 1B Chair: David Rappaport | ||
|
Convexifying star-shaped polygons H. Everett, S. Lazard, S. Robbins, H. Schröder, S. Whitesides |
10:30 |
Towards a realistic upper bound for the number of facets of 3-dimensional Dirichlet stereohedra
Daciana Bochis, Francisco Santos |
|
| On reconfiguring tree linkages: trees can lock
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides |
10:50 |
Hyperplane depth and nested simplices
William Steiger, Rephael Wenger | |
|
On point covers of c-oriented polygons
Frank Nielsen |
11:10 |
Planar sets with few empty convex polygons
Adrian Dumitrescu | |
|
Removing degeneracies by perturbing the problem or perturbing the world
Pierre Alliez, Olivier Devillers, Jack Snoeyink |
11:30 |
A shrinking-circle sweep-algorithm to construct the farthest site Delaunay diagram in the plane
B. Adam, P. Kauffmann, D. Schmitt, J.-C. Spehner | |
|
| |||
| Lunch break |
12:00- 14:00 |
Lunch break | |
|
| |||
| Leacock Room 26 | |||
|
Open Problem Session Chair: William Moser |
14:00 | ||
|
| |||
| Coffee break | 15:00 | ||
|
| |||
|
Leacock Room 26 Session 2A Chair: Binay Bhattacharya | Leacock Room 219 Session 2B Chair: Hazel Everett | ||
|
Quantile approximation for robust statistical estimation
David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth Silverman, Angela Y. Wu |
15:30 |
Parallel edge flipping
Ferran Hurtado, Marc Noy, Jorge Urrutia | |
|
Finding specified sections of arrangements: 2D results
P. Bose, F. Hurtado, H. Meijer, S. Ramaswami, D. Rappaport, V. Sacristán, T. Shermer, G. Toussaint |
15:50 |
On a disjoint quadrilateral partition for a given point set
Kiyoshi Hosono, Masatsugu Urabe | |
|
Constructing median constrained minimum spanning tree
J. Bhadury, R. Chandrasekharan, L. Gewali |
16:10 |
A modified longest side bisection triangulation
Christoph Stamm, Stephan Eidenbenz, Renato Pajarola | |
|
Constrained facility location
Ferran Hurtado, Vera Sacristán, Godfried Toussaint |
16:30 |
Computational geometry on the grid: traversal and planesweep algorithms for spatial applications
Markus Schneider, Ralf H. Güting, Thomas de Ridder | |
|
| |||
|
Leacock Room 26 Session 3A Chair: Godfried Toussaint | Leacock Room 219 Session 3B Chair: Jörg-Rüdiger Sack | ||
|
(presentation cancelled)
|
09:10 |
Subexponential-time algorithms for minimum weight triangulation and related problems
Andrzej Lingas | |
|
Hiding disks in folded polygons
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Godfried T. Toussaint |
09:30 |
Computational investigations of the optimality of two- and three-dimensional triangulations under several criteria
Akira Tajima, Hiroshi Imai | |
|
Balanced partitions of two sets of points in the plane
Atushi Kaneko, M. Kano |
09:50 |
Guarding in a simple polygon
Bor-Kuan Lu, Fang-Rong Hsu, Chuan Yi Tang | |
|
Geometric tree graphs of points in the plane
M.C. Hernando, F. Hurtado, A. Márquez, M. Mora, M. Noy |
10:10 |
Characterizing LR-visibility polygons and related problems
Binay K. Bhattacharya, Subir Kumar Ghosh | |
|
| |||
| Coffee break | 10:30 | ||
|
| |||
|
Leacock Room 26 Chair: Sue Whitesides | |||
| Invited Speaker Joe Marks, Mitsubishi Electric Research Laboratories Graphics Made Easier Through Optimization and Computational Geometry |
11:00 |
||
|
| |||
| Lunch break | 12:00- 14:00 |
||
|
| |||
|
Leacock Room 26 Session 4A Chair: Rephael Wenger | Leacock Room 219 Session 4B Chair: Tom Shermer | ||
|
Separating objects in the plane with wedges and strips
Ferran Hurtado, Marc Noy, Pedro A. Ramos, Carlos Seara |
14:00 |
Illuminating triangles and quadrilaterals with vertex floodlights
Felipe Contreras, Jurek Czyzowicz, Nicolas Fraiji, Jorge Urrutia | |
|
Intersecting general parametric surfaces using bounding volumes
Ernst H. Huber |
14:20 |
Shortest paths and visibility inside triangulated curved polygons with applications to conic visibility
Jesús García-López, Pedro A. Ramos | |
|
On the time bound for convex decomposition of simple polygons
Mark Keil, Jack Snoeyink |
14:40 |
The exact cost of exploring streets with a CAB
Alejandro López-Ortiz, Sven Schuierer | |
|
On measuring areas of polygons
J. Czyzowicz, F. Contreras-Alcalá, J. Urrutia |
15:00 |
Inapproximability of some art gallery problems
Stephan Eidenbenz, Christoph Stamm, Peter Widmayer | |
|
| |||
| Coffee break | 15:20 | Coffee break | |
|
| |||
|
Leacock Room 26 Session 5A Chair: Prosenjit Bose | Leacock Room 219 Session 5B Chair: Sylvain Lazard | ||
|
On the multiple label placement problem
Konstantinos G. Kakoulis, Ioannis G. Tollis |
15:50 |
Some problems on approximation of set of points by polygonal curves
J. Miguel Díaz, Francisco Gómez, Ferran Hurtado | |
|
Dynamic maintenance and visualization of molecular surfaces
Chandrajit Bajaj, Valerio Pascucci, Robert Holt, Arun Netravali |
16:10 |
No Steiner point subdivision simplification is NP-complete
Regina Estkowski | |
|
Unfolding some classes of orthogonal polyhedra
Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, Steve Robbins, Sue Whitesides |
16:30 |
A coarse grained parallel solution to terrain simplification
M. Ghodsi, J-R. Sack | |
|
An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
Danny Z. Chen, Jinhui Xu |
16:50 |
(presentation cancelled)
| |
|
| |||
| Coffee break | 17:10 | ||
|
| |||
| Leacock Room 26 | |||
| Business Meeting | 17:30 | ||
|
| |||
|
Leacock Room 26 Session 6A Chair: Suneeta Ramaswami | Leacock Room 219 Session 6B Chair: Steve Robbins | ||
|
Towards a contour morphing preserving differentiability
Antonio A. F. de Oliviera, Luiz Marcos G. Gonçalves, Claudio Esperança |
09:30 |
Power diagram depth sorting
Paolo Cignoni, Leila De Floriani | |
|
Maintaining partitions of dynamic planar meshes
L.G. Aleksandrov, H.N. Djidjev |
09:50 |
Euclidean proximity and power diagrams
Leonidas J. Guibas, Li Zhang | |
|
Recovering lines with fixed linear probes
Mark de Berg, Jit Bose, David Bremner, William Evans, Lata Narayanan |
10:10 |
Dynamic additively weighted Voronoi diagrams made easy
François Anton, Darka Mioc, Christopher Gold | |
|
| |||
| Coffee break | 10:30 | ||
|
| |||
|
Leacock Room 26
Chair: David Avis | |||
| Invited Speaker Vasek Chvátal, Rutgers University Solving Travelling Salesman Problems |
11:00 |
||
|
| |||
| Lunch break | 12:00- 14:00 |
||
|
| |||
|
Leacock Room 26 Session 7A Chair: Therese Biedl | Leacock Room 219 Session 7B Chair: David Bremner | ||
|
Cutting rectangles in equal area pieces
Prosenjit Bose, Jurek Czyzowicz, Dominic Lessard |
14:00 |
Delaunay-type triangulation in the dually flat space
Kensuke Onishi | |
|
Aperture-angle optimization problems in 3 dimensions
Elsa Omaña-Pulido, Godfried T. Toussaint |
14:20 |
On the total correctness of Lawson's oriented walk algorithm
Frank Weller | |
|
Detection of text-line orientation
Prosenjit Bose, Jean-Denis Caron, Kilani Ghoudi |
14:40 |
A note on checking proximity graphs
Guiseppe Liotta | |
|
Perspective projections and removal of degeneracies
Francisco Gómez, Ferran Hurtado, Toni Sellarès, Godfried Toussaint |
15:00 |
The size of the open sphere of influence graph in L-(infinity) metric spaces
Michael Soss | |
|
| |||
| Coffee break | 15:20 | Coffee break | |
|
| |||
|
Leacock Room 26 Session 8A Chair: Vasek Chvátal | Leacock Room 219 Session 8B Chair: Mike Soss | ||
|
Geometric clustering models for multimedia databases
Mary Inaba, Hiroshi Imai |
15:50 |
Proximity drawings of binary trees in polynomial area
P. Penna, P. Vocca | |
|
A framework for memory-efficient levels of detail
André Guéziec, Gabriel Taubin |
16:10 |
Straight-line embeddings of three rooted trees in the plane
Atsushi Kaneko, M. Kano, Shin-ichi Tokunaga | |
|
Perfect divisions of a cake
Jin Akiyama, Gisaku Nakamura, Eduardo Rivera-Campo, Jorge Urrutia |
16:30 | ||
|
| |||
| Closing dance party at Thomson House. | 20:00- 00:00 | ||
|
| |||
