The following 45 papers have been accepted to the 23rd Annual ACM Symposium on Computational Geometry. There were 139 submissions.

- A Data Structure for Multi-Dimensional Range Reporting

Yakov Nekrich - A Geometric Framework for Solving Subsequence Problems in Computational Biology Efficiently

Thorsten Bernholt, Friedrich Eisenbrand, and Thomas Hofmeister - A New Upper Bound for Embedding 3-Polytopes on the Grid

Ares Ribó, Günter Rote, and André Schulz - A PTAS for k-Means Clustering Based on Weak Coresets

Dan Feldman, Morteza Monemizadeh, and Christian Sohler - A Space-Optimal Data-Stream Algorithm for Coresets in the Plane

Pankaj K. Agarwal and Hai Yu - An Optimal Generalization of the Centerpoint Theorem, and its Extensions

Nabil H. Mustafa and Saurabh Ray - Aperture-Angle and Hausdorff-Approximation of Convex Figures

Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, and Mira Lee - Approximating the centroid is hard

Luis Rademacher - Between Umbra and Penumbra

Julien Demouth, Olivier Devillers, Hazel Everett, Sylvain Lazard, and Raimund Seidel - Computing the Volume of the Union of Cubes

Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir - Constant-Factor Bicriteria Linear-time Approximations for Generalized k-Mean/Median/Center

Dan Feldman, Amos Fiat, and Micha Sharir - Decomposition of Multiple Coverings into Several Parts

Janos Pach and Geza Toth - Distributed Computation of Virtual Coordinates

Mirela Ben-Chen, Craig Gotsman, and Camille Wormser - Embeddings of Moving Points in Euclidean Space

Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu - Finding Bounded-Curvature Paths in Narrow Simply Connected Regions

Jonathan Backer and David Kirkpatrick - Fully Dynamic Geometric Spanners

Liam Roditty - Guard Placement For Wireless Localization

David Eppstein, Michael T. Goodrich, and Nodari Sitchinava - Hardness of Minkowski Addition and Related Operations

Hans Raj Tiwary - Kinetic kd-Trees and Longest-Side kd-Trees

Mohammad Ali Abam, Mark de Berg, and Bettina Speckmann - Happy Endings for Flip Graphs

David Eppstein - Line Transversals to Disjoint Balls

Ciprian Borcea, Xavier Goaoc, and Sylvain Petitjean - Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes

Jean-Daniel Boissonnat, Leonidas J. Guibas, and Steve Y. Oudot - New Upper Bounds on the Quality of PCA Bounding Boxes in R
^{2}and R^{3}

Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote - Offline Variants of the ``Lion and Man'' Problem

Adrian Dumitrescu, Ichiro Suzuki, and Pawel Zylinski - On Approximate Halfspace Range Counting and Relative ε-Approximations

Boris Aronov, Sariel Har-Peled, and Micha Sharir - On Approximate Range Counting and Halfspace Depth

Peyman Afshani and Timothy Chan - On Regular Vertices on the Union of Planar Objects

Esther Ezra, Janos Pach, and Micha Sharir - On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

Efi Fogel and Dan Halperin - On the Number of k-rich Transformations

Jozsef Solymosi and Gabor Tardos - Optimal Simplification of Polygonal Chain for Rendering

Lilian Buzer - Pareto envelopes in R
^{3}under l_{1}and l_{∞}distance functions

Victor Chepoi and Karim Nouioua - Probabilistic Embeddings of Bounded Genus Graphs Into Planar Graphs

Piotr Indyk and Anastasios Sidiropoulos - Quadratic and Cubic B-Splines by Generalizing Higher-Order Voronoi Diagrams

Yuanxin Liu and Jack Snoeyink - Querying Approximate Shortest Paths in Anisotropic Regions

Siu-Wing Cheng and Hyeon-Suk Na and Antoine Vigneron and Yajun Wang - Shortest Paths on Realistic Polyhedra

Yevgeny Schreiber - Similar Simplices in a d-dimensional Point Set

Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, and Micha Sharir - Snap Rounding of Bézier Curves

Arno Eigenwillig, Lutz Kettner, and Nicola Wolpert - Streaming Algorithms for Line Simplification

Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, and Alireza Zarei - The Theory of Multidimensional Persistence

Gunnar Carlsson and Afra Zomorodian - The Voronoi Diagram of Three Lines in 3D

Hazel Everett, Daniel Lazard, Sylvain Lazard, and Mohab Safey El Din - There Are Not Too Many Magic Configurations

Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote - Thick Non-Crossing Paths and Minimum-Cost Flows in Polygonal Domains

Joseph S. B. Mitchell and Valentin Polishchuk - Tight Bounds for Dynamic Convex Hull Queries

Erik D. Demaine and Mihai Patrascu - Traversing a Set of Points with a Minimum Number of Turns

Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, and Pavel Valtr - Weak ε-nets have a basis of size O(1/ε) in any dimension

Nabil H. Mustafa and Saurabh Ray

Ooooooooooooh! There were quite a few papers there that sound Very Interesting to my ears.

On the other hand, the Gunnar Carlsson brand of applied algebraic topology is something I like very much, so I probably shouldn't be too surprised.

Posted by: Michi | February 07, 2007 at 12:11 PM