SoCG 2002 Call for participation

Vera Sacristan vera at
Fri Mar 1 19:34:28 PST 2002

                         CALL FOR PARTICIPATION

We are pleased to announce that the registration for the 18th ACM Symposium 
on Computational Geometry which will be held at the Universitat Politècnica 
de Catalunya, Barcelona, Spain, June 5-7, is now open, and we would like to 
encourage participation to this significant event.

The conference website at


contains registration form, accomodation form, preliminary program
(an ASCII version is attached below), general information about the
conference, local information, as well as details about the CGAL User 
Workshop on June 4th.

The early registration deadline is May 12, but we would like to encourage 
you to register as soon as possible, as accomodation will be reserved on a 
first-come-first-served basis, and finding a hotel room in Barcelona,
a very popular touristic destination, is not at all a trivial matter.

We are looking forward to seeing you in Barcelona!

Ferran Hurtado and Vera Sacristán
Conference Chairs

Preliminary Program

JUNE 4th

18:00 - 20:00   Reception and registration

JUNE 5th

 8:30 -  9:00   Late registration
 9:00 - 10:20   Session 1
                - Parametric Search Made Practical, Rene van Oostrum and
Remco C. Veltkamp
                - 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
                - On the Crossing Number of Complete Graphs, Oswin
Aichholzer, Franz
                  Aurenhammer and Hannes Krasser
                - On the Number of Embeddings of Minimally Rigid Graphs,
Ciprian Borcea
                  and Ileana Streinu
10:20 - 10:50   Coffee break
10:50 - 11:50   Session 2
                - Deforming Necklaces, Leonidas J. Guibas, An Nguyen, Daniel
Russel and Li Zhang
                - Efficient Maintenance and Self-Collision Testing for
Kinematic Chains,
                  Itay Lotan and Fabian Schwarzer and Dan Halperin and
Jean-Claude Latombe
                - Box-Trees for Collision Checking in Industrial
Installations, H.J.
                  Haverkort and M. de Berg and J. Gudmundsson
11:50 - 12:00   Small break
12:00 - 13:00   INVITED TALK 1

13:00 - 15:00   Lunch

15:00 - 16:00   Session 3
                - Finding the Consensus Shape for a Protein Family, L. Paul
Chew and Klara Kedem
                - Paper Position Sensing, Marshall Bern and David Goldberg
                - A Global Approach to Automatic Solution of Jigsaw Puzzles,
                  Goldberg and Christopher Malon and Marshall Bern
16:00 - 16:15   Coffee break
16:15 - 17:15   Open Problems
17:30 - 20:30   Social event: Gaudí Tour

JUNE 6th

 9:00 - 10:20   Session 4
                - The Power of Subtraction in Geometric Searching, Bernard
                - A lower bound on the distortion of embedding planar
metrics into
                  Euclidean space, Ilan Newman and Yuri Rabinovich
                - The One-Round Voronoi Game, Otfried Cheong, Sariel
                  Nathan Linial and Jiri Matousek
                - Approximate Nearest Neighbor Algorithms for Frechet
Distance via
                  Product metrics, Piotr Indyk
10:20 - 10:50   Coffee break
10:50 - 11:50   Session 5
                - Point-Line Incidences in Space, Micha Sharir and Emo Welzl
                - Incidences Between Points and Circles in Three Dimensions,
                  Aronov, Vladlen Koltun and Micha Sharir
                - Lenses in Arrangements of Pseudo-circles and their
Applications, Eran
                  Nevo, Janos Pach, Rom Pinchasi, Micha Sharir and Shakhar
11:50 - 12:00   Small break
12:00 - 13:00   INVITED TALK 2

13:00 - 15:00   Lunch

15:00 - 16:20   Session 6
                - Guaranteed-Quality Parallel Delaunay Refinement for
                  Polyhedral Domains, Demian Nave and Nikos Chrisochoides
and Paul Chew
                - The Delaunay Tetrahedralization from Delaunay Triangulated
                  Sunghee Choi
                - Quickest Paths, Straight Skeletons, and the City Voronoi
Diagram, Oswin
                  Aichholzer and Franz Aurenhammer and Belen Palop
                - Testing Homotopy for Paths in the Plane, Sergio Cabello,
Yuanxin Liu
                  and Jack Snoeyink
16:20 - 16:50   Coffee break
16:50 - 17:50   Session 7
                - Pseudo Approximation Algorithms, with Applications to
Optimal Motion
                  Planning, Tetsuo Asano, David Kirkpatrick and Chee Yap
                - Kinetic Maintenance of Context-Sensitive Hierarchical
                  of Disjoint Simple Polygons , David Kirkpatrick and
Bettina Speckmann
                - Interlocked Open Linkages with Few Joints,
                  Erik D. Demain, Stefan Langerman, Joseph O'Rourke and Jack
18:00 - 19:00   Business meeting
20:30 -         Social event: Conference Dinner

JUNE 7th

 9:00 - 10:20   Session 8
                - Conforming Delaunay Triangulations in 3D, David
Cohen-Steiner and Eric
                  Colin de Verdiere and Mariette Yvinec
                - The Probabilistic Complexity of the Voronoi Diagram of
Points on a
                  Polyhedron, Mordecai J. Golin and Hyeon-Suk Na
                - Three Dimensional Euclidean Voronoi Diagrams of Lines with
a Fixed
                  Number of Orientations, Vladlen Koltun and Micha Sharir
                - Polyhedral Voronoi Diagrams of Polyhedra in Three
Dimensions, Vladlen
                  Koltun and Micha Sharir
10:20 - 10:50   Coffee break
10:50 - 11:50   Session 9
                - Vertex-Unfolding of Simplicial Manifolds, Erik D. Demaine
and David
                  Eppstein and Jeff Erickson and George W. Hart and Joseph
                - Optimally Cutting a Surfce into a Disk, Jeff Erickson and
Sariel Har-Peled
                - Optimal Decomposition of Polygonal Models into Triangle
Strips, Regina
                  Estkowski, Joseph S.B. Mitchell and Xinyu Xiang
11:50 - 12:00   Small break
12:00 - 13:00   INVITED TALK 3

13:00 - 15:00   Lunch

15:00 - 16:00   Videos session
                - Exact Minkowski Sums and Applications, Eyal Flato, Efi
Fogel, Dan Halperin,
                  and Eran Leiserowitz
                - Homotopy Techniques for Real-Time Visualization of
Geometric Tangent
                  Problems, Daniel Kotzor and Thorsten Theobald
                - Growing Fat Graphs, Alon Efrat, Stephen Kobourov, Martin
Stepp, and
                  Carola Wenk
                - AUTO-FOLLOW: Getting a Piece of the Action All the Time,
Alexander Bogomjakov
                  and Craig Gotsman
                - Adventures of Moebius Band, Stanislav Klimenko, Gregory M.
Nielson, Lialia
                  Nikitina, and Igor Nikitin
16:00 - 16:30   Coffee break
16:30 - 17:50   Session 10
                - Improved Construction of Vertical Decompositions of
                  Arrangements, Hayim Shaul and Dan Halperin
                - Cost Prediction for Ray Tracing, B. Aronov and H.
Bronnimann and A.Y.
                  Chang and Y.-J. Chiang
                - Visibility Preserving Terrain Simplification - An
Experimental Study,
                  Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell and
Yuval Nir
                - Projective Clustering in High Dimensions Using Core-Sets,
                  Har-Peled and Kasturi R. Varadarajan
17:50           Conference concludes

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