ACM Symposium on Computional Geometry 2001: Conference Program

dls at dls at
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   
         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.

 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

 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

   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 

 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
    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>


The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list