ACM Symposium on Computional Geometry 2001: Conference Program
dls at eecs.tufts.edu
dls at eecs.tufts.edu
Sun Mar 25 23:07:16 PST 2001
*************************************************************
The 15th Annual ACM Symposium on Computational Geometry
Tufts University
Medford/Somerville, Massachusetts
June 3-5, 2001
http://www.eecs.tufts.edu/EECS/scg01
http://www.eecs.tufts.edu/EECS/scg01/prog.ps
Sponsored by ACM SIGACT and SIGGRAPH
With support from Tufts University and MERL
*************************************************************
Saturday, June 2
Optional Cruises of Boston Harbour: 1:00 p.m. & 3:00 p.m.
Cocktail Hour and Registration: 6:00 - 8:00 pm
Sunday, June 3
Session 1
9:00 On the Number of Congruent Simplices in a Point Set:
Pankaj K. Agarwal (Duke); Micha Sharir (Tel Aviv & NYU)
9:20 Enumerating Order Types for Small Point Sets with Applications
O. Aichholzer, F. Aurenhammer, H. Krasser (Graz U. of Technology)
9:40 The Union of Congruent Cubes in Three Dimensions:
Janos Pach (CUNY, NYU, Hungarian Acad. of Sciences) Ido Safruti
(Tel Aviv) Micha Sharir (Tel Aviv & NYU)
10:00 Different Distances of Planar Point Sets:
Jozsef Solymosi, Csaba David Toth (ETH Z)
Refreshment break
Session 2
10:40 Schematization of Road Networks: Sergio Cabello, Mark de
Berg, Steven van Dijk, Marc van Kreveld, Tycho Strijk (Utrecht)
11:00 Simplifying a Polygonal Subdivision While Keeping it Simple:
Regina Estkowski (HRL Labs) Joseph S. B. Mitchell (SUNY Stony Brook)
11:20 Hardware-Assisted View-Dependent Map Simplification
Nabil Mustafa (Duke) Eleftheris Koutsofios, Shankar Krishnan,
Suresh Venkatasubraminian (AT&T Research)
11:40 Efficient Perspective-Accurate Silhouette Computation and
Applications: Mihai Pop (TIGR) Gill Barequet (Technion) Christian
A. Duncan (U. Miami) Michael T. Goodrich, Wenjing Huang, Subodh
Kumar (Johns Hopkins)
Lunch: 12:00 pm
Invited Talk
1:30 Sphere Packings and Generative Programming: Thomas Hales (U.
Michigan)
Session 3
2:45 Hierarchical Morse Complexes for Piecewise Linear 2-Manifolds:
Herbert Edelsbrunner (Duke & Raindrop Geomagic) John Harer (Duke)
Afra Zomorodian (UI Urbana-Champaign)
3:05 Computing a Canonical Polygonal Schema of an Orientable Triang-
ulated Surface: Francis Lazarus (CNRS & U. Poitiers) Michel
Pocchiola (Ecole Normale Superieure) Gert Vegter (Groningen) Anne
Verroust (INRIA, Rocquencourt)
3:25 Area-Preserving Piecewise-Affine Transformations: Alan Saalfeld
(Ohio-State)
Refreshment Break
Session 4
4:15 Nice Point Sets Can Have Nasty Delaunay Triangulations:
Jeff Erickson (UI Urbana-Champaign)
4:35 Walking in a Triangulation: Olivier Devillers, Sylvain Pion,
Monique Teillaud (INRIA, Sophia Antipolis)
4:55 Sink-insertion for Mesh Improvement: Herbert Edelsbrunner (Duke)
Damrong Guoy (UI Urbana-Champaign)
Business Meeting: 5:30 pm, Cabot Auditorium
Monday, June 4
Session 5
9:00 Box-Trees and R-Trees with Near-Optimal Query Time: Pankaj K.
Agarwal (Duke) Mark de Berg (Utrecht) Joachim Gudmundsson, Mikael
Hammar (Lund U.) Herman J. Havekort (Utrecht)
9:20 A Segment-Tree Based Kinetic BSP: Mark de Berg (Utrecht)
Joao Comba, Leonidas J. Guibas (Stanford)
9:40 Binary Space Partitions for Axis-Parallel Segments, Rectangles,
and Hyperrectangles: Adrian Dumitrescu, Joseph S. B. Mitchell
(SUNY Stony Brook) Micha Sharir (Tel Aviv & NYU )
10:00 A Note on Binary Plane Partitions: Csaba David Toth (ETH Z)
Refreshment Break
Session 6
10:40 Exact Nearest Neighbor Search in High Dimensions: Helmut Alt,
Laura Heinrich-Litan (Freie U. Berlin)
11:00 Farthest Neighbors and Center Points in the Presence of
Rectangular Obstacles: Boaz Ben-Moshe, Matthew J. Katz
(Ben-Gurion) Joseph S. B. Mitchell (SUNY Stony Brook)
11:20 A Fully Dynamic Algorithm for Planar Width: Timothy M. Chan
(U. Waterloo)
11:40 A Practical Approach for Computing the Diameter of a Point-Set
Sariel Har-Peled (UI Urbana-Champaign)
Lunch: 12:00 pm
Invited Talk
1:30 Protein Geometry as a Function of Time: Fred Richards (Yale)
Session 7
2:45 Discrete Mobile Centers: Jie Gao, Leonidas J. Guibas (Stanford)
John Hershberger (Mentor Graphics) Li Zhang (Compaq Systems Research)
An Zhu (Stanford)
3:05 Segment Intersection Searching Problems in General Settings:
Vladlen Koltun (Tel Aviv)
3:25 On the Complexity of Halfspace Area Queries: Stefan Langerman
(Rutgers)
Refreshment Break
Session 8
4:15 Algorithms for Congruent Sphere Packing and Applications
Danny Z. Chen, Xiaobo {Sharon} Hu, Yingping Huang, Yifan Li
(Notre Dame) Jinhui Xu (SUNY Buffalo)
4:35 polymake: an Approach to Modular Software Design in Computational
Geometry: Ewgenij Gawrilow, Michael Joswig (TU-Berlin)
4:55 A Randomized Art-Gallery Algorithm for Sensor Placement
Hector Gonzalez-Banos, Jean-Claude Latombe (Stanford
Barbecue 6:00 pm: Gather on the lawn between Lewis and Tilton
Halls for an outdoor cookout with blankets, frisbees, and
volleyball (weather permitting) followed by music by blues
band DEEP FREYED , featuring Bill Frey, Matt Dickerson, Daniel
Scharstein, and special guest.
Tuesday, June 5
Session 9
9:00 Notes on Computing Peaks in k-Levels and Parametric Spanning Trees:
Naoki Katoh ( Kyoto U.) Takeshi Tokuyama (Tohoku U.)
9:20 Geometric Permutations of Fat Objects: Matthew Katz (Ben-Gurion)
Kasturi Varadarajan (U. Iowa)
9:40 The Clarkson-Shor Technique Revisited and Extended:
Micha Sharir (Tel Aviv & NYU)
10:00 Detecting Undersampling in Surface Reconstruction:
Tamal K. Dey, Joachim Giesen (Ohio State)
Refreshment Break
Session 10
10:40 Computing the Intersection of Quadrics: Exactly and Actually!
Nicola Geismann (Saarlandes) Michael Hemmer, Elmar Schoemer (Max
Planck Saarbruecken)
11:00 PRECISE: Efficient Multiprecision Evaluation of Algebraic Roots
and Predicates for Reliable Geometric Computation: S. Krishnan
(AT&T Research) M. Foskey (UNC) T. Culver (Think3) J. Keyser
(Texas A ) D. Manocha (UNC)
Invited Talk
11:30 Computational Geometry for Sculpture: George W. Hart
http://www.georgehart.com/
Lunch: 12:30 pm
Session 11
2:00 New Bounds on the Betti Numbers of Semi-Algebraic Sets and
Arrangements of Real Algebraic Hypersurfaces: Saugata Basu (Georgia
Tech)
2:20 Efficient and Small Representation of Line Arrangements with
Applications: David P. Dobkin (Princeton) Ayellet Tal (Technion)
2:40 A Sum of Squares Theorem for Visibility Complexes
Pierre Angelier, Michel Pocchiola (Ecole Normale Sup
Short Break
3:15 Monotone Paths in Line Arrangements: Rados Radoicic
(MIT) Geza Toth (MIT & Hungarian Acad. of Sciences)
3:35 Balanced Lines, Halving Triangles, and the Generalized Lower Bound
Theorem: Micha Sharir (Tel Aviv & NYU) Emo Welzl (ETH Z)
Refreshment Break: 4:00 - 4:30 pm
Optional: Boston Red Sox vs Detroit Tigers, 7:30 p.m. at Fenway Park
******************************************************************
10th Annual Video Review of Computational Geometry
The video review showcases advances in the use of algorithm animation,
visualization, and interactive computing in the study of computational
geometry. The video review tape is distributed to all registrants
at the conference and will subsequently be available from ACM.
* Small Representation of Line Arrangements: Ayellet Tal (Technion),
David Dobkin (Princeton)
* The convex hull of ellipsoids: Nicola Geismann (Saarlandes) Michael
Hemmer, Elmar Schomer (Max Planck Saarbruecken)
* 2-point site Voronoi Diagram: Gill Barequet (Technion), Matthew
Dickerson (Middlebury) Robert Drysdale (Dartmouth)
* The Connectivity Shapes Video: Martin Isenburg (UNC), Stefan Gumhold
(Tubingen), Craig Gotsman (Technion)
* A prototype system for Visualizing Time-Dependent Data: Lutz Kettner,
Jack Snoeyink (UNC)
************************************************************************
Theoretical Track Program Committee: Applied Track Program Committee:
Boris Aronov (Polytechnic U, Brooklyn) Nancy Amato (Texas A&M)
Otfried Cheong (Utrecht U) Karl Bo"hringer (U Washington, Seattle)
Jesu's De Loera (UC Davis) Franca Gianini (IMA, Genova)
David Eppstein, Chair (UC Irvine) Lutz Kettner (UNC Chapel Hill)
Sariel Har-Peled (UI Urbana Champaign) Dan Halperin, Chair (Tel Aviv U)
Piotr Indyk (MIT) Kurt Mehlhorn (MPII, Saarbru"cken)
Edgar A. Ramos (MPII Saarbru"cken) Mark Overmars (Utrecht U)
Ileana Streinu (Smith College) Seth Teller (MIT)
Peter Widmayer (ETH Zurich)
Video Review Committee Mariette Yvinec (INRIA Sophia-Antipolis)
Jonathan Cohen (Johns Hopkins)
Herbert Edelsbrunner (Duke)
Subodh Kumar (Johns Hopkins) Conference Chair
Ming C. Lin (UNC Chapel Hill)
Dinesh Manocha, Chair (UNC Chapel Hill) Diane L. Souvaine (Tufts U)
Amitabh Varshney (U of Maryland) <scg01 at eecs.tufts.edu>
*******************************************************************************
-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce
mailing list