Preliminary Program

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

16th Annual ACM Symposium on Computational Geometry 2000
scg00@cs.ust.hk