|
22nd Annual ACM Symposium on Computational Geometry | |
|
| June 5-7 2006, Sedona, Arizona | |||
| Program |
 |
| Sunday, June 4 (Canyon Patio) |
| 19:00 | Welcome reception and registration |
| Monday, June 5 (Canyon Ballroom) |
| 8:00 | Registration and light breakfast |
| 9:00 | Opening |
| 9:10-10:30 | Session 1 (Chair: Nina Amenta) |
| Minimum Weight Triangulation is NP-hard Wolfgang Mulzer and Günter Rote |
|
| The Effect of Corners on the Complexity of Approximate Range Searching S. Arya, T. Malamatos and D. M. Mount |
|
| Efficient Algorithm for Approximating Maximum Inscribed Sphere in High
Dimensional Polytope Yulai Xie, Jack Snoeyink and Jinhui Xu |
|
| An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in
Three Dimensions Yevgeny Schreiber and Micha Sharir |
|
| 10:30-11:00 | Multimedia Coffee Break |
| Geometry-Based Reasoning for a Large Sensor Network Sándor P. Fekete and Alexander Kröller |
|
| Projective clustering and its application to surface reconstruction Amit Mhatre and Piyush Kumar |
|
| A Portable Algorithm Visualization System with Dynamic
Camera Positioning for Tracking 3D Geometric Objects Ming-Hung Tsai, Jyh-DaWei, Jeng-Hung Huang and D. T. Lee |
|
| Streaming Computation of Delaunay Triangulations Martin Isenburg, Yuanxin (Leo) Liu, Jonathan Shewchuk, and Jack Snoeyink |
|
| Finding a Shortest k-Link Path in a Weighted Subdivision Ovidiu Daescu, Joseph S.B. Mitchell, Simeon Ntafos, James D. Palmer, and Chee K. Yap |
|
| On Approximating the Smallest Enclosing Bregman Balls Frank Nielsen and Richard Nock |
|
| 11:00-12:00 | Invited Talk: Mathieu Desbrun Discrete Differential Forms and Applications to Surface Tiling |
| 12:00-14:00 | Lunch |
| 14:00-15:00 | Session 2 (Chair: Otfried Cheong) |
| Conflict-Free Colorings of Shallow Discs Noga Alon and Shakhar Smorodinsky |
|
| How to Play a Coloring Game Against a Color-Blind Adversary Ke Chen |
|
| Colored Intersection Searching via Sparse Rectangular Matrix Multiplication Haim Kaplan, Micha Sharir and Elad Verbin |
|
| 15:00-15:20 | Coffee Break |
| 15:20-16:20 | Session 3 (Chair: Sue Whitesides) |
| Locked and Unlocked Chains of Planar Shapes Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó Mor and Günter Rote | |
| Refolding Planar Polygons Hayley N. Iben, James F. O'Brien and Erik D. Demaine |
|
| Computing the Frechet Distance Between Simple Polygons in Polynomial Time Kevin Buchin, Maike Buchin and Carola Wenk |
|
| 16:20-16:40 | Coffee Break |
| 16:40-17:40 | Session 4 (Chair: Alper Üngör) |
| Ray Shooting and Intersection Searching Amidst Fat Convex Polyhedra in
3-Space Boris Aronov, Mark de Berg and Chris Gray |
|
| On the ICP Algorithm Esther Ezra, Micha Sharir and Alon Efrat |
|
| An upper bound on the average size of silhouettes Marc Glisse |
|
| 17:45 | Business meeting |
| Tuesday, June 6 (Canyon Ballrooms A and B) |
| 8:00 | Registration and light breakfast | ||
| 9:00-10:15 | Session 5A (Chair: Yusu Wang) | 9:00-10:15 | Session 5B (Chair: Carola Wenk) |
| Topology guaranteeing manifold reconstruction using distance function to noisy data Frédéric Chazal and André Lieutier |
A fast k-means implementation using coresets Gereon Frahling and Christian Sohler | ||
| Vines and Vineyards by Updating Persistence in Linear Time David Cohen-Steiner, Herbert Edelsbrunner and Dmitriy Morozov |
On the worst case complexity of the k-means method David Arthur and Sergei Vassilvitskii | ||
| Persistence-Sensitive Simplification of Functions on 2-Manifolds Herbert Edelsbrunner, Dmitriy Morozov and Valerio Pascucci |
Lower bounds on Locality Sensitive Hashing Rajeev Motwani, Assaf Naor and Rina Panigrahy | ||
| 10:15-10:45 | Multimedia Coffee Break | ||
| Geometry-Based Reasoning for a Large Sensor Network Sándor P. Fekete and Alexander Kröller |
|||
| Projective clustering and its application to surface reconstruction Amit Mhatre and Piyush Kumar |
|||
| A Portable Algorithm Visualization System with Dynamic
Camera Positioning for Tracking 3D Geometric Objects Ming-Hung Tsai, Jyh-DaWei, Jeng-Hung Huang and D. T. Lee |
|||
| Streaming Computation of Delaunay Triangulations Martin Isenburg, Yuanxin (Leo) Liu, Jonathan Shewchuk, and Jack Snoeyink |
|||
| Finding a Shortest k-Link Path in a Weighted Subdivision Ovidiu Daescu, Joseph S.B. Mitchell, Simeon Ntafos, James D. Palmer, and Chee K. Yap |
|||
| On Approximating the Smallest Enclosing Bregman Balls Frank Nielsen and Richard Nock |
|||
| 10:45-12:00 | Session 6A (Chair: Matt Dickerson) | 10:45-12:00 | Session 6B (Chair: Ken Clarkson) |
| Simple and Semi-Dynamic Structures for Cache-Oblivious Planar Orthogonal Range Searching Lars Arge and Norbert Zeh |
Embedding Ultrametrics Into Low-Dimensional Spaces Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos | ||
| I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis Pankaj K. Agarwal, Lars Arge and Ke Yi |
Plane Embeddings of Planar Graph Metrics MohammadHossein Bateni, Erik D. Demaine, Mohammad Taghi Hajiaghayi and Mohammad Moharrami | ||
| On Realistic Terrains Esther Moet, Marc van Kreveld and A. Frank van der Stappen |
Volume distortion for subsets of Euclidean spaces James R. Lee | ||
| 12:00-13:30 | Lunch | ||
| 13:30-14:45 | Session 7A (Chair: Sylvain Pion) | 13:30-14:45 | Session 7B (Chair: Dominique Attali) |
| Complete Subdivision Algorithms, I: Intersection of Bezier Curves Chee K. Yap |
The Orienteering Problem in the Plane Revisited Ke Chen and Sariel Har-Peled | ||
| The predicates for the Voronoi diagram of ellipses Ioannis Z. Emiris, George M. Tzoumas and Elias P. Tsigaridas |
Degenerate Crossing Numbers Janos Pach and Geza Toth | ||
| An approximate arrangement algorithm for semi-algebraic curves Victor Milenkovic and Elisha Sacks |
On the maximum number of edges in topological graphs with no four pairwise crossing edges Eyal Ackerman | ||
| 14:45-15:15 | Coffee Break | ||
| 15:15-16:30 | Session 8A (Chair: Sue Whitesides) | 15:15-16:30 | Session 8B (Chair: Alper Üngör) |
| The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets Rolf Klein and Martin Kutz |
Engineering a Compact Parallel Delaunay Algorithm in 3D Daniel K. Blandford, Guy E. Blelloch and Clemens Kadow | ||
| Random Triangulations of Point Sets Micha Sharir and Emo Welzl |
Minimum-Cost Load-Balancing Partitions Boris Aronov, Paz Carmi and Matthew J. Katz | ||
| Pre-Triangulations and Liftable Complexes Oswin Aichholzer, Franz Aurenhammer and Thomas Hackl |
Optimal Succinct Representations of Planar Maps Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer | ||
| 17:00 | Excursion / Conference Dinner | ||
| Wednesday, June 7 (Canyon Ballroom) |
| 8:00 | Registration and light breakfast |
| 9:00-10:20 | Session 9 (Chair: Dominique Attali) |
| A Sampling Theory for Compacts in Euclidean Space Frédéric Chazal, David Cohen-Steiner and André Lieutier | |
| Medial Axis Approximation and Unstable Flow Complex Joachim Giesen, Edgar A. Ramos and Bardia Sadri | |
| Provably Good Sampling and Meshing of Lipschitz Surfaces Jean-Daniel Boissonnat and Steve Oudot | |
| Sliver Removal by Lattice Refinement François Labelle | |
| 10:20-11:40 | Coffee Break |
| 10:40-12:00 | Session 10 (Chair: Sylvain Pion) |
| Improved Output-Sensitive Snap Rounding John Hershberger | |
| Iterated Snap Rounding with Bounded Drift Eli Packer | |
| Hole Detection or: 'How much Geometry hides in Connectivity?' Stefan Funke and Christian Klein | |
| Online Geometric Reconstruction Bernard Chazelle and Seshadhri Comandur | |
| 12:00-14:00 | Lunch |
| 14:00-15:00 | Session 11 (Chair: Ken Clarkson) |
| On Overlays and Minimization Diagrams Vladlen Koltun and Micha Sharir | |
| On How to Get Close to the Median Shape Sariel Har-Peled | |
| Envelope surfaces Nico Kruithof and Gert Vegter | |
| 15:00-15:20 | Coffee Break |
| 15:20-16:20 | Session 12 (Chair: Alon Efrat) |
| Splitting (Complicated) Surfaces Is Hard Erin Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus and Kim Whittlesey | |
| Computing Shortest Non-Contractible Cycles on Surfaces of Bounded
Genus in Almost Linear Time Martin Kutz | |
| Tight Bounds for Connecting Sites Across Barriers David Krumme, Eynat Rafalin, Diane L. Souvaine and Csaba D. Tóth | |
| 16:20-16:40 | Coffee Break |
| 16:40-17:40 | Session 13 (Chair: Yusu Wang) |
| Minimum-Cost Coverage of Point Sets by Disks Helmut Alt, Esther M. Arkin, Herv'e Brönnimann, Jeff Erickson, Sándor Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell and Kim Whittlesey | |
| Algorithms for Two-Box Covering Esther M. Arkin, Gill Barequet and Joseph S. B. Mitchell | |
| Exact Computation of Protein Structure Similarity L. Paul Chew |