SoCG 24

List of Accepted Papers

The following 42 papers (ordered by date of submission) have been accepted to the 24th Annual Symposium on Computational Geometry. There were 127 submissions.

  • Markov convexity and local rigidity of distorted metrics,
    Manor Mendel and Assaf Naor
  • Polychromatic Colorings of Plane Graphs,
    Noga Alon, Robert Berke, Maike Buchin, Kevin Buchin, Peter Csorba, Saswata Shannigrahi, Bettina Speckmann and Philipp Zumstein
  • Consistent Digital Rays,
    Jinhee Chun, Matias Korman, Martin Nöllenburg and Takeshi Tokuyama
  • Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space,
    Eitan Yaffe and Dan Halperin
  • Fast Enumeration Algorithms for Non-crossing Geometric Graphs,
    Naoki Katoh and Shin-ichi Tanigawa
  • Optimizing Active Ranges for Consistent Dynamic Map Labeling,
    Ken Been, Martin Nöllenburg, Sheung-Hung Poon and Alexander Wolff
  • On the Complexity of Checking Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism,
    Hans Raj Tiwary and Khaled Elbassioni
  • Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs,
    Victor Chepoi, Feodor Dragan, Bertrand Estellon, Michel Habib and Yann Vaxes
  • Maximum Thick Paths in Static and Dynamic Environments,
    Esther Arkin, Joseph Mitchell and Valentin Polishchuk
  • Helly-type theorems for approximate covering,
    Julien Demouth, Olivier Devillers, Marc Glisse and Xavier Goaoc
  • On s-intersecting curves and related problems,
    Sarit Buzaglo, Ron Holzman and Rom Pinchasi
  • A Simple and Efficient Kinetic Spanner,
    Mohammad Ali Abam, Mark de Berg and Joachim Gudmundsson
  • Towards Persistence-Based Reconstruction in Euclidean Spaces,
    Frederic Chazal and Steve Oudot
  • Tighter Bounds for Random Projections of Manifolds,
    Ken Clarkson
  • Circular Partitions with Applications to Visualization and Embeddings,
    Krzysztof Onak and Anastasios Sidiropoulos
  • Markov Incremental Constructions,
    Bernard Chazelle and Wolfgang Mulzer.
  • Self-Improving Algorithms for Delaunay Triangulations,
    Kenneth L. Clarkson and C. Seshadhri
  • Robust construction of the three-dimensional flow complex,
    Frederic Cazals, Aditya Parameswaran and Sylvain Pion
  • Reeb Spaces of Piecewise Linear Mappings,
    Herbert Edelsbrunner, John Harer and Amit Patel
  • New Existence Proofs for ε-Nets,
    Evangelia Pyrga and Saurabh Ray
  • External memory planar point location with logarithmic updates,
    Lars Arge, Gerth Stølting Brodal and S. Srinivasa Rao
  • Exact Geometric-Topological Analysis of Algebraic Surfaces,
    Eric Berberich, Michael Kerber and Michael Sagraloff
  • Discrete Laplace Operator on Meshed Surfaces,
    Misha Belkin, Jian Sun and Yusu Wang
  • Predicates for Line Transversals to Lines and Line Segments in Three-dimensional Space,
    Olivier Devillers, Marc Glisse and Sylvain Lazard
  • Schnyder woods for higher genus triangulated surfaces,
    Luca Castelli Aleardi, Eric Fusy and Thomas Lewiner
  • Testing Contractibility in Planar Rips Complexes,
    Erin Chambers, Jeff Erickson and Pratik Worah
  • Intersecting convex sets by rays,
    Rado Fulek, Andreas Holmsen and János Pach
  • The Complexity of the Outer Face in Arrangements of Random Segments,
    Noga Alon, Dan Halperin, Oren Nechushtan and Micha Sharir
  • Delaunay triangulations of imprecise points in linear time after preprocessing,
    Maarten Löffler and Jack Snoeyink
  • Walking Your Dog in the Woods in Polynomial Time,
    Erin Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus and Shripad Thite
  • Locally Uniform Anisotropic Meshing,
    Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec
  • Extremal problems on triangle areas in two and three dimensions,
    Adrian Dumitrescu, Micha Sharir and Csaba Toth
  • A (Slightly) Faster Algorithm for Klee's Measure Problem,
    Timothy M. Chan
  • Dynamic Coresets,
    Timothy M. Chan
  • On Levels in Arrangements of Curves, III: Further Improvements,
    Timothy M. Chan
  • Embedding and Similarity Search for Point Sets under Translation,
    Minkyoung Cho and David Mount
  • Coloring Kk-free intersection graphs of geometric objects in the plane,
    Jacob Fox and Janos Pach
  • Hinged Dissections Exist,
    Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine and Scott D. Kominers
  • Improved upper bounds on the crossing number,
    Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood
  • I/O Efficient Algorithms for Computing Contour Lines on a Terrain,
    Pankaj Agarwal, Lars Arge, Thomas Mølhave and Bardia Sadri
  • Untangling triangulations through local explorations,
    Pankaj Agarwal, Bardia Sadri and Hai Yu
  • Combinatorial Genericity and Minimal Rigidity,
    Ileana Streinu and Louis Theran

-   SoCG08 Home   -