Sunday, June 11 | |
6:00 | Reception University Centre, Multi Purpose Hall |
Monday, June 12 | |
Session 1, Applied Track Steve Fortune | |
9:00 |
Mesh Generation for Domains with Small Angles. Jonathan R. Shewchuk, UC Berkeley |
9:20 |
Triangulations in CGAL. Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec, INRIA |
9:40 |
Improving the Surface Cycle Structure for Hexahedral
Mesh Generation. Matthias Müller-Hannemann, TU Berlin |
10:00 |
Computing with Integer Points inMinkowski Sums. Ioannis Z. Emiris, INRIA |
Coffee break: 10:20 am - 10:50 am | |
Invited talk | |
10:50 |
Between Theory and Commercialization. Ping Fu, Raindrop Geomagic |
Lunch: 11:50 am - 1:30 pm | |
Session 2, Theory Track Pankaj Agarwal | |
1:30 |
Point Sets with Many k-Sets. Géza Tóth, MIT |
1:50 |
An Improved Bound for k-Sets in Three Dimensions. Micha Sharir, Shakhar Smorodinsky, Tel Aviv U.; Gábor Tardos, Hungarian Academy |
2:10 |
Origin-Embracing Distributions or A Continuous Analogue of
the Upper Bound Theorem. Uli Wagner and Emo Welzl, ETH Zürich |
2:30 |
A Helly-Type Theorem for Hyperplane Transversals to
Well-Separated Convex Sets. Boris Aronov, Poly U.; Jacob E. Goodman, City College, CUNY; Richard Pollack, Courant Inst.; Rephael Wenger, Ohio State |
2:50 |
A Trace Bound for the Hereditary Discrepancy. Bernard Chazelle and Alexey Lvov, Princeton |
Coffee break: 3:10 pm - 3:40 pm | |
Session 3, Theory/Applied Track Herbert Edelsbrunner | |
3:40 |
On the Continuous Weber and k-Median Problems. Sándor P. Fekete, TU Berlin; Joseph S.B. Mitchell, SUNY Stony Brook; Karin Weinbrecht, U. Köln |
4:00 |
The 2-Center Problem with Obstacles. Dan Halperin, Micha Sharir, Tel Aviv U.; Ken Goldberg, UC Berkeley |
4:20 |
Random Sampling in Geometric Optimization: New Insights and
Applications. Bernd Gärtner and Emo Welzl, ETH Zürich |
4:40 |
The Analysis of a Simple k-Means Clustering Algorithm. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, U. Maryland; Christine Piatko, Johns Hopkins; Ruth Silverman, U. of the District of Columbia; Angela Y. Wu, American U. |
5:00 |
An Efficient, Exact, and Generic Quadratic Programming Solver for
Geometric Optimization. Bernd Gärtner, ETH Zürich; Sven Schönherr, FU Berlin |
5:20 |
Accurate and Efficient Unions of Balls. Nina Amenta and Ravi Kolluri, UT Austin |
Business meeting: 8 pm University Centre, Multipurpose Hall | |
Tuesday, June 13 | |
Session 4, Applied Track Stefan Schirra | |
9:00 |
Fast Software for Box Intersections. Afra Zomorodian, UI Urbana Champaign; Herbert Edelsbrunner, Duke U. and Raindrop Geomagic |
9:20 |
Algebraic Methods and Arithmetic Filtering for Exact
Predicates on Circle Arcs. Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud, INRIA |
9:40 |
Pitfalls in Computing with Pseudorandom Determinants. Bernd Gärtner, ETH Zürich |
10:00 |
LOOK -- A Lazy Object-Oriented Kernel for Geometric Computation. Stefan Funke and Kurt Mehlhorn, MPI |
Coffee: 10:20 am - 10:50 am | |
Invited talk | |
10:50 |
Computational Geometry helps Computer Cartography?. Andrew Frank, Technical University Vienna |
Lunch: 11:50 am - 1:30 pm | |
Session 5, Theory Track Mark de Berg | |
1:30 |
When Crossings Count -- Approximating the Minimum Spanning Tree. Sariel Har-Peled, Duke U.; Piotr Indyk, Stanford U. |
1:50 |
Linear Programming Queries Revisited. Edgar A. Ramos, MPI |
2:10 |
Point Set Labeling with Specified Positions. Srinivas Doddi, U. New Mexico; Madhav V. Marathe, Los Alamos; Bernard M.E. Moret, U. New Mexico |
2:30 |
I/O-Efficient Dynamic Planar Point Location. Lars Arge, Duke U.; Jan Vahrenhold, U. Münster |
2:50 |
Linear-Time Triangulation of a Simple Polygon Made
Easier Via Randomization. Nancy M. Amato, Texas A&M; Michael T. Goodrich, JHU; Edgar A. Ramos, MPI |
Coffee: 3:10 pm - 3:40 pm | |
Session 6, Applied/Theory Track Christopher Gold | |
3:40 |
A Simple Algorithm for Homeomorphic Surface Reconstruction. Nina Amenta and Sunghee Choi, UT Austin; Tamal K. Dey and Naveen Leekha, Ohio State |
4:00 |
Smooth Shape Reconstruction via Natural Neighbor
Interpolation of Distance Functions. Jean-Daniel Boissonnat and Frédéric Cazals, INRIA |
4:20 |
Reconstructing Curves with Sharp Corners. Tamal K. Dey and Rephael Wenger, Ohio State |
4:40 |
Voronoi-Based Interpolation with Higher Continuity. Hisamoto Hiyoshi and Kokichi Sugihara, U. Tokyo |
Conference Banquet: 7 pm | |
Wednesday, June 14 | |
Session 7, Applied/Theory Track Dan Halperin | |
9:00 |
Reachability by Paths of Bounded Curvature in Convex Polygons. Hee-kap Ahn and Otfried Cheong, HKUST; Jirí Matousek, Charles U.; Antoine Vigneron, HKUST |
9:20 |
An Algorithm for Searching a Polygonal Region with a Flashlight. Steven M. Lavalle, Borislav Simov, and Giora Slutzki, Iowa State |
9:40 |
Computing Approximate Shortest Paths on Convex Polytopes. Pankaj K. Agarwal and Sariel Har-Peled, Duke U.; Meetesh Karia, Trilogy |
10:00 |
Densest Translational Lattice Packing of Non-Convex Polygons. Victor J. Milenkovic, U. Miami |
Coffee: 10:20 am - 10:50 am | |
Session 8, Theory Track Franz Aurenhammer | |
10:50 |
Deterministic Algorithms for 3-D Diameter
and some 2-D Lower Envelopes. Edgar A. Ramos, MPI |
11:10 | Approximating the Diameter, Width,Smallest Enclosing Cylinder, andMinimum-Width Annulus. Timothy M. Chan, U. Waterloo |
11:30 |
Testing the Congruence of d-Dimensional Point Sets. Peter Braß and Christian Knauer, FU Berlin |
Lunch: 11:50 am - 1:30 pm | |
Invited talk | |
1:30 |
Randomized Motion Planning. Jean-Claude Latombe, Stanford University |
Coffee: 2:30 pm - 3:00 pm | |
Session 9, Theory Track Hazel Everett | |
3:00 |
Multivariate Regression Depth. Marshall Bern, Xerox; David Eppstein, UC Irvine |
3:20 |
Kinetic Collision Detection for Simple Polygons. David Kirkpatrick, UBC; Jack Snoeyink, UNC Chapel Hill; Bettina Speckmann, UBC |
3:40 |
Kinetic Connectivity for Unit Disks. Leonidas Guibas, Stanford U.; John Hershberger, Mentor Graphics; Subhash Suri, Washington U.; Li Zhang, Stanford U. |
Coffee: 4:00 pm - 4:20 pm | |
Session 10, Theory Track Jeff Erickson | |
4:20 |
Delaunay Triangulations and Voronoi Diagrams for Riemannian
Manifolds. Greg Leibon, Dartmouth; David Letscher, Oklahoma State |
4:40 |
Sweep Algorithms for Constructing Higher-Dimensional
Constrained Delaunay Triangulations. Jonathan R. Shewchuk, UC Berkeley |
5:00 |
Cutting Glass. János Pach, CUNY; Gábor Tardos, Hungarian Academy |