2002 Symposium on Computational Geometry---Accepted Papers

[Subhash Suri]

------------------------------------------------------------------------
SoCG '02 Accepted Papers
------------------------------------------------------------------------

1.  Conforming Delaunay Triangulations in 3D, David Cohen-Steiner and Eric
Colin de Verdiere and Mariette Yvinec

2.  Quickest Paths, Straight Skeletons, and the City Voronoi Diagram, Oswin
Aichholzer and Franz Aurenhammer and Belen Palop

3.  Paper Position Sensing, Marshall Bern and David Goldberg

4.  A Global Approach to Automatic Solution of Jigsaw Puzzles, David
Goldberg and Christopher Malon and Marshall Bern

5.  The Power of Subtraction in Geometric Searching, Bernard Chazelle

6.  Finding the Consensus Shape for a Protein Family, L. Paul Chew and Klara
Kedem

7.  Guaranteed-Quality Parallel Delaunay Refinement for Restricted
Polyhedral Domains, Demian Nave and Nikos Chrisochoides and Paul  Chew

8.  Vertex-Unfolding of Simplicial Manifolds, Erik D. Demaine and David
Eppstein and Jeff Erickson and George W. Hart

9.  The Probabilistic Complexity of the Voronoi Diagram of Points on a
Polyhedron, Mordecai J. Golin and Hyeon-Suk Na

10.  Improved Construction of Vertical Decompositions of Three-Dimensional
Arrangements, Hayim Shaul and Dan Halperin

11.  Cost Prediction for Ray Tracing, B. Aronov and H. Bronnimann and A.Y.
Chang and Y.-J. Chiang

12.  Box-Trees for Collision Checking in Industrial Installations, H.J.
Haverkort and M. de Berg and J. Gudmundsson

13.  A lower bound on the distortion of embedding planar metrics into
Euclidean space, Ilan Newman and Yuri Rabinovich

14.  Approximate Nearest Neighbor Algorithms for Frechet Distance via
Product Metrics, Piotr Indyk

15.  Efficient Maintenance and Self-Collision Testing for Kinematic Chains,
Itay Lotan and Fabian Schwarzer and Dan Halperin and Jean-Claude Latombe

16.  Optimally Cutting a Surfce into a Disk, Jeff Erickson and Sariel
Har-Peled

17.  Optimal Decomposition of Polygonal Models into Triangle Strips, Regina
Estkowski, Joseph S.B. Mitchell and Xinyu Xiang

18.  Deforming Necklaces, Leonidas J. Guibas, An Nguyen, Daniel Russel and
Li Zhang

19.  Testing Homotopy for Paths in the Plane, Sergio Cabello, Yuanxin Liu
and Jack Snoeyink

20.  Visibility Preserving Terrain Simplification -- An Experimental Study,
Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell and Yuval Nir

21.  Three Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed
Number of Orientations, Vladlen Koltun and Micha Sharir

22.  Point-Line Incidences in Space, Micha Sharir and Emo Welzl

23.  Incidences Between Points and Circles in Three Dimensions, Boris
Aronov, Vladlen Koltun and Micha Sharir

24. Lenses in Arrangements of Pseudo-circles and their Applications, Eran
Nevo, Janos Pach, Rom Pinchasi, Micha Sharir and Shakhar Smorodinsky

25.  A Local Search Approximation Algorithm for k-Means Clustering, Tapas
Kanungo, David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth
Silverman and Angela Y. Wu

26. On the Crossing Number of Complete Graphs, Oswin Aichholzer, Franz
Aurenhammer and AHannes Krasser

27. The One-Round Voronoi Game, Otfried Cheong, Sariel Har-Peled, Nathan
Linial and Jiri Matousek

28.  Parametric Search Made Practical, Rene van Oostrum and Remco C.
Veltkamp

29.  Projective Clustering in High Dimensions Using Core-Sets, Sariel
Har-Peled and Kasturi R. Varadarajan

30.  Interlocked Open Linkages with Few Joints, Erik D. Demain, Stefan
Langerman, Joseph O'Rourke and Jack Snoeyink

31.  Kinetic Maintenance of Context-Sensitive Hierarchical Representations
of Disjoint Simple Polygons , David Kirkpatrick and Bettina Speckmann

32.  On the Number of Embeddings of Minimally Rigid Graphs, Ciprian Borcea
and Ileana Streinu

33.  The Delaunay Tetrahedralization from Delaunay Triangulated Surfaces,
Sunghee Choi

34.  Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions, Vladlen
Koltun and Micha Sharir

35.  Pseudo Approximation Algorithms, with Applications to Optimal Motion
Planning, Tetsuo Asano, David Kirkpatrick and Chee Yap


Chandrajit Bajaj and Subhash Suri
Program Committee Co-Chairs


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