Papers accepted to 21st Annual Symposium on Computational Geometry

[jsbm at ams.sunysb.edu]

Dear Colleagues,

We are pleased to announce the list of papers accepted 
to the 21st Annual Symposium on Computational Geometry,
which will be held this year in Pisa, Italy, on June 6-8, 2005.
See http://www.socg05.org/  for conference details.

This year, the program committee selected 41 papers for presentation
from among 140 submissions.  The competition was stiff, due to the
overall high quality of the research papers submitted.

We thank the members of the Program Committee and the 
numerous referees who assisted in the review process!

We hope to see you all in Pisa in June.

Best,

Joe Mitchell and Guenter Rote, co-chairs, PC

Program Committee:
Tetsuo Asano, Therese Biedl, Paul Chew, Alon Efrat,
Sandor Fekete, Craig Gotsman, Ferran Hurtado, Vladlen Koltun,
Joe Mitchell, Guenter Rote, Micha Sharir, Bettina Speckmann, Monique Teillaud

*** Accepted Papers ****


A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions
Har-Peled, Ungor

Abstract Order Type Extension and New Results on the Rectilinear Crossing Number
Aichholzer, Krasser

Almost Tight Bound for a Single Cell in an Arrangement of Convex Polyhedra in R^3
Ezra

An Exact, Complete and Efficient Implementation for Computing Planar Maps 
    of Quadric Intersection Curves
Berberich, Hemmer, Kettner, Schoemer, Wolpert

Cache-Oblivious Planar Orthogonal Range Searching and Counting
Arge, Brodal, Fagerberg, Laustsen

Cache-Oblivious R-Trees
Arge, de Berg, Haverkort

Certifying and Constructing Minimally Rigid Graphs in the Plane
Bereg

Critical Points of the Distance to an epsilon-Sampling on a Surface and 
   Flow Complex Reconstruction
Dey, Giesen, Ramos, Sadri

Curvature-bounded traversals of narrow corridors
Bereg, Kirkpatrick

Dynamic Maintenance of Molecular Surfaces under Conformational Changes
Eyal, Halperin

Efficient Computation of Query Point Visibility in Polygons with Holes
Zarei, Ghodsi

Energy-Aware Stage Illumination
Eisenbrand, Funke, Karrenbauer, Matijevic

Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
Har-Peled, Mendel

Finding the best shortcut in a geometric network
Farshi, Giannopoulos, Gudmundsson

Forbidden Patterns and Unit Distances
Pach, Tardos

Guarding a Terrain by Two Watchtowers
Agarwal, Bereg, Daescu, Kaplan, Ntafos, Zhu

Hadwiger and Helly-Type Theorems for Disjoint Unit Spheres in R^3
Cheong, Goaoc, Holmsen

Improved Approximation Algorithms for Geometric Set Cover
Clarkson, Varadarajan

Incidences of not too degenerate hyperplanes
Elekes, Toth

Inclusion-Exclusion Formulas for Independent Complexes
Attali, Edelsbrunner

Inequalities for the Curvature of Curves and Surfaces
Cohen-Steiner, Edelsbrunner

Kinetic Sorting and Kinetic Convex Hull
Abam, de Berg

Learning Surfaces by Probing
Boissonnat, Guibas, Oudot

Maximizing the Overlap of Two Planar Convex Sets under Rigid Motions
Ahn, Cheong, Park, Shin, Vigneron

Minimum Dilation Stars
Eppstein, Wortman

Mountain Reduction, Block Matching, and Medical Applications
Chen, Hu, Luan, Wang

Multi-Pass Geometric Algorithms
Chan, Chen

On the Exact Computation of the Topology of Real Algebraic Curves
Seidel, Wolpert

Pointed and Colored Binary Encompassing Trees
Hoffmann, Toth

Provable Dimension Detection using Principal Component Analysis
Cheng, Wang, Wu

Sampling in Dynamic Data Streams and Applications
Frahling, Indyk, Sohler

Shortest Path amidst Disc Obstacles is Computable
Chang, Choi, Kwon, Park, Yap

Smaller Coresets for k-Median and k-Means Clustering
Har-Peled, Akash Kushal

Space Efficient Dynamic Orthogonal Range Reporting
Nekrich

Stability of Persistence Diagrams
Cohen-Steiner, Edelsbrunner, Harer

Star Splaying: An Algorithm for Repairing Delaunay Triangulations and Convex Hulls
Shewchuk

The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data
Eppstein, Goodrich, Sun

The Visibility-Voronoi Complex and Its Applications
Wein, van den Berg, Halperin

The lifting model for reconfiguration
Bereg, Dumitrescu

Vertical Ray Shooting for Fat Objects
de Berg

Weak feature size and persistent homology: computing homology of solids in R^n from noisy data samples
Chazal, Lieutier



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