Accepted papers

The following 45 papers have been accepted to the 23rd Annual 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 Ribo', Gu"nter Rote, and Andre' 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, and Joachim Gudmundsson

• 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, Danny Segev, 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² and R³
  Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Gu"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³ under l₁ 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 Be'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 Gu"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