|
Saturday, June 7, 2003
|
|
7:00−9:00pm
|
Reception (Terrace Pavilion)
|
|
Sunday, June 8, 2003
|
|
Session: Geometric Graphs
|
|
9:00-10:00
|
|
9:00
|
Fault-Tolerant Geometric Spanners
Artur Czumaj and Hairong Zhao (New Jersey Inst of Tech)
|
|
9:20
|
Euclidean Bounded-Degree Spanning Tree Ratios
Timothy M. Chan (Univ of Waterloo)
|
|
9:40:
|
Approximation Algorithms for Aligning Points
Sergio Cabello and Marc van Kreveld (Utrecht Univ)
|
|
|
10:00-10:25
|
Coffee Break
|
|
Session: Approximation
|
|
10:25-11:25
|
|
10:25
|
Shape Fitting with Outliers
Sariel Har-Peled (Univ of Illinois) and Yusu Wang (Duke Univ)
|
|
10:45
|
High-Dimensional Shape Fitting in Linear Time
Sariel Har-Peled (Univ of Illinois) and Kasturi R. Varadarajan (Univ of Iowa)
|
|
11:05
|
Smooth Kinetic Maintenance of Clusters
John Hershberger (Mentor Graphics)
|
|
|
Video and Multimedia Session
|
|
11:30-12:30
|
5 minute short presentations of the
videos
|
|
12:30-2:00
|
Lunch
|
|
Session: Applications
|
|
2:00-3:20
|
|
2:00
|
Polygon Decomposition Based on the Straight Line Skeleton
Mirela Tanase and Remco Veltkamp (Utrecht Univ)
|
|
2:20
|
Efficient Algorithms for Shared Camera Control
Sariel Har-Peled (Univ of Illinois), Vladlen Koltun, Dezhen Song, and Ken Goldberg
(Univ California, Berkeley)
|
|
2:40
|
Good NEWS: Partitioning a Simple Polygon by Compass Directions
Marc van Kreveld and Iris Reinbacher (Utrecht Univ)
|
|
3:00
|
Geometric Algorithms for Static Leaf Sequencing Problems in Radiation Therapy
Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Chao Wang (Univ of Notre Dame),
and Xiaodong Wu (Univ of Texas, Pan American)
|
|
|
3:20-4:00
|
Coffee Break
|
|
Session: Combinatorial Geometry
|
|
4:00-5:20
|
|
4:00
|
Topological Graphs with No Self-intersecting Cycle of Length 4
Rom Pinchasi and Rados Radoicic (MIT)
|
|
4:20
|
Distinct Distances in Homogeneous Sets
Jozsef Solymosi and Van Vu (Univ California, San Diego)
|
|
4:40
|
A Tight Bound for the Number of Different Directions in Three Dimensions
Janos Pach (NYU), Rom Pinchasi (MIT), and Micha Sharir (Tel Aviv Univ)
|
|
5:00
|
On Conflict-Free Coloring of Points and Simple Regions in the Plane
Sariel Har-Peled (Univ of Illinois) and Shakhar Smorodinsky (Tel Aviv Univ)
|
|
|
5:45-7:00
|
FCRC: Turing Award Lecture (Grand Ballroom)
|
Monday, June 9, 2003
|
|
Session: Partitions and Arrangements
|
|
9:00-10:00
|
|
9:00
|
Long Monotone Paths in Line Arrangements
Jozsef Balogh (Ohio State Univ), Oded Regev (Princeton Univ), Clifford
Smyth (Carnegie Mellon Univ), William Steiger, and Mario Szegedy (Rutgers Univ)
|
|
9:20
|
New Constructions for Weak Epsilon-Nets
Jiri Matousek (Charles Univ) and Uli Wagner (ETH Zürich)
|
|
9:40
|
Curve-Sensitive Cuttings
Vladlen Koltun (Univ California, Berkeley) and Micha Sharir (Tel Aviv Univ)
|
|
|
10:00-10:25
|
Coffee Break
|
|
Session: Motion and Pseudotriangulations
|
|
10:25-11:25
|
|
10:25
|
Spatial Embedding of Pseudo-Triangulations
Oswin Aichholzer (Graz Univ), Franz Aurenhammer (Graz Univ), Peter Braß
(Freie Univ Berlin), and Hannes Krasser (Graz Univ)
|
|
10:45
|
Planar Minimally Rigid Graphs and Pseudo-Triangulations
Ruth Haas (Smith College), David Orden (Univ Cantabria), Günter
Rote (Freie Univ Berlin), Francisco Santos (Univ Cantabria), Brigitte
Servatius, Hermann Servatius (Worcester Poly Univ), Diane Souvaine
(Tufts Univ), Ileana Streinu (Smith College), and Walter Whiteley
(York Univ)
|
|
11:05
|
The Complexity of (Un)folding
Helmut Alt, Christian Knauer, Günter Rote (Freie Univ Berlin), and Sue
Whitesides (McGill Univ)
|
|
|
11:30-12:30
|
FCRC: Plenary Talk (Grand Ballroom)
|
|
12:30-2:00
|
Lunch
|
|
Session: Models and Meshes
|
|
2:00-3:40
|
|
2:00
|
Local Polyhedra and Geometric Graphs
Jeff Erickson (Univ of Illinois)
|
|
2:20
|
Updating and Constructing Constrained Delaunay and Constrained Regular
Triangulations by Flips
Jonathan Richard Shewchuk (Univ of California, Berkeley)
|
|
2:40
|
Anisotropic Voronoi Diagrams and Guaranteed-Quality Anisotropic Mesh Generation
François Labelle and Jonathan Richard Shewchuk (Univ of California, Berkeley)
|
|
3:00
|
Complexity of the Delaunay Triangulation of Points on Surfaces: The Smooth Case
Dominique Attali (Lab LIS), Jean-Daniel Boissonnat (INRIA
Sophia-Antipolis), and André Lieutier (LMC-IMAG)
|
|
3:20
|
Incremental Constructions con BRIO
Nina Amenta (Univ of California, Davis), Sunghee Choi (Univ Texas, Austin),
and Günter Rote (Freie Univ Berlin)
|
|
|
3:40-4:00
|
Coffee Break
|
|
Session: Data Structures
|
|
4:00-5:00
|
|
4:00
|
Proximate Planar Point Location
John Iacono (Polytechnic Univ) and Stefan Langerman (Univ Libre de
Bruxelles)
|
|
4:20
|
Cost-Driven Octree Construction Schemes: An Experimental Study
Boris Aronov, Hérvé Brönnimann, Allen Y. Chang, and Yi-Jen Chiang
(Polytechnic Univ)
|
|
4:40
|
On Cache-Oblivious Multidimensional Range Searching
Pankaj Agarwal, Lars Arge, Andrew Danner, and Bryan Holland-Minkley
(Duke Univ)
|
|
|
5:00-6:00
|
FCRC: Knuth Prize Lecture (San Diego)
|
|
6:10-7:10
|
Business Meeting (Pacific 1 & 2)
|
Tuesday, June 10, 2003
|
|
Session: Numerical Issues and Robustness
|
|
9:00-10:00
|
|
9:00
|
Near-Optimal Parameterization of the Intersection of Quadrics
Laurent Dupont (LORIA), Daniel Lazard (Univ Paris), Sylvain Lazard,
and Sylvain Petitjean (LORIA)
|
|
9:20
|
Constructive Root Bound for k-Ary Rational Input Numbers
Sylvain Pion and Chee Yap (NYU)
|
|
9:40
|
Controlled Perturbation for Arrangements of Circles
Dan Halperin and Eran Leiserowitz (Tel Aviv Univ)
|
|
|
10:00-10:25
|
Coffee Break
|
|
Session: Optimization
|
|
10:25-11:25
|
|
10:25
|
Optimized Color Gamuts for Tiled Displays
Marshall Bern (Palo Alto Research Ctr) and David Eppstein (Univ of
California, Irvine)
|
|
10:45
|
Hausdorff Distance under Translation for Points, Disks, and Balls
Pankaj K. Agarwal (Duke Univ), Sariel Har-Peled (Univ of Illinois),
Micha Sharir (Tel Aviv Univ), and Yusu Wang (Duke Univ)
|
|
11:05
|
The Smallest Enclosing Ball of Balls: Combinatorial Structure and Algorithms
Bernd Gärtner and Kaspar Fischer (ETH Zürich)
|
|
|
11:30-12:30
|
FCRC: Plenary Talk (Grand Ballroom)
|
|
12:30-2:00
|
Lunch (On your own)
|
|
Session: Curve and Surface Reconstruction
|
|
2:00-3:20
|
|
2:00
|
Curve Reconstruction from Noisy Samples
Siu-Wing Cheng (HKUST), Stefan Funke (MPI Saarbruecken), Mordecai
Golin (HKUST), Piyush Kumar (SUNY), Sheung-Hung Poon (HKUST), and
Edgar Ramos (Univ of Illinois)
|
|
2:20
|
Restricted Delaunay Triangulations and Normal Cycle
David Cohen-Steiner and Jean-Marie Morvan (INRIA Sophia-Antipolis)
|
|
2:40
|
Estimating Surface Normals in Noisy Point Cloud Data
Niloy J. Mitra and An Nguyen (Stanford Univ)
|
|
3:00
|
Shape Dimension and Intrinsic Metric from Samples of Manifolds with High Co-dimension
Joachim Giesen and Uli Wagner (ETH Zürich)
|
|
|
3:20-4:00
|
Coffee Break
|
|
Session: Topology
|
|
4:00-5:20
|
|
4:00
|
An Optimal Algorithm for the Minimum Edge Cardinality Cut Surface Problem
David E. Cardoze (Carnegie Mellon Univ)
|
|
4:20
|
Loops in Reeb Graphs of 2-Manifolds
Kree Cole-McLaughlin (Lawrence Livermore Natl Lab), Herbert
Edelsbrunner, John Harer, Vijay Natarajan (Duke Univ), and
Valerio Pascucci (Lawrence Livermore Natl Lab)
|
|
4:40
|
Molecular Shape Analysis Based upon the Morse-Smale Complex and the Connolly Function
Frédéric Cazals (INRIA), Frédéric Chazal
(Univ de Bourgogne), and Thomas Lewiner (INRIA)
|
|
5:00
|
Morse Complexes for Piecewise Linear 3-Manifolds
Herbert Edelsbrunner, John Harer, Vijay Natarajan (Duke U), and
Valerio Pascucci (Lawrence Livermore Natl Lab)
|
|
