SoCG 2005 Accepted Papers

[The following message is from Joe Mitchell by email. Congratulations to all the accepted authors, and thanks to the committee for their hard work! —Jeff]

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, Üngör

• 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³
  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³
  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ⁿ from noisy data samples
  Chazal, Lieutier