Tuesday, February 16, 2010

SoCG accepted papers

After the Valentine's day massacre, comes the list. I'll link to PDFs if I'm pointed to them (add in the comments)
  • David Millman and Jack Snoeyink. Computing Planar Voronoi Diagrams in Double Precision: An Example of Degree-driven Algorithm Analysis
  • György Elekes and Micha Sharir. Incidences in Three Dimensions and Distinct Distances in the Plane
  • Micha Sharir, Adam Sheffer and Emo Welzl. On Degrees in Random Triangulations
  • Pankaj K. Agarwal, Rinat Ben Avraham and Micha Sharir. The 2-Center Problem in Three Dimensions
  • Florian Berger and Rolf Klein. A Traveller's Problem
  • Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number hard
  • Tobias Christ, Dömötör Pálvölgyi and Miloš Stojaković. Consistent digital line segments
  • Dominique Attali and Andre Lieutier. Optimal reconstruction might be hard
  • Dominique Attali and Andre Lieutier. Reconstructing shapes with guarantees by unions of convex sets
  • Mark de Berg. Better Bounds on the Union Complexity of Locally Fat Objects
  • Marc Glisse and Sylvain Lazard. On the complexity of the sets of free lines and free line segments among balls in three dimensions
  • Tamal Dey, Jian Sun and Yusu Wang. Approximating loops in a shortest homology basis from point data
  • Mohammad Ali Abam and Sariel Har-Peled. New Constructions of SSPDs and their Applications
  • Sergio Cabello, Éric Colin de Verdière and Francis Lazarus. Output-sensitive algorithm for the edge-width of an embedded graph
  • Sergio Cabello, Éric Colin de Verdière and Francis Lazarus. Finding Shortest Non-Trivial Cycles in Directed Graphs on Surfaces
  • David Eppstein and Elena Mumford. Steinitz Theorems for Orthogonal Polyhedra
  • Akitoshi Kawamura, Jiri Matousek and Takeshi Tokuyama. Zone diagrams in Euclidean spaces and other normed spaces
  • Eryk Kopczynski, Igor Pak and Piotr Przytycki. Acute triangulations of polyhedra and the space
  • Keiko Imai, Akitoshi Kawamura, Jiri Matousek, Daniel Reem and Takeshi Tokuyama. Distance k-sectors exist
  • Joseph Mitchell. A Constant-Factor Approximation Algorithm for TSP with Neighborhoods in the Plane
  • Benjamin A. Burton. The complexity of the normal surface solution space
  • Karl Bringmann. Klee's Measure Problem on Fat Boxes in Time $O(n^{(d+2)/3})$
  • Natan Rubin. Lines Avoiding Balls in Three Dimensions Revisited
  • Pankaj K. Agarwal, Jie Gao, Leonidas Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin and Micha Sharir. Kinetic Stable Delaunay Graphs
  • Haim Kaplan, Micha Sharir and Natan Rubin. A Kinetic Triangulation Scheme For Moving Points in The Plane
  • Anne Driemel, Sariel Har-Peled and Carola Wenk. Approximating the \Frechet Distance for Realistic Curves in Near Linear Time
  • Joachim Gudmundsson and Pat Morin. Planar Visibility: Testing and Counting
  • Ken-ichi Kawarabayashi, Stephan Kreutzer and Bojan Mohar. Linkless and flat embeddings in 3-space and the Unknot problem
  • Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, Torsten Ueckerdt and Ran Ziv. Points with Large Quadrant-Depth
  • Sunil Arya, David Mount and Jian Xia. Tight Lower Bounds for Halfspace Range Searching
  • Don Sheehy, Benoit Hudson, Gary Miller and Steve Oudot. Topological Inference via Meshing
  • Gur Harary and Ayellet Tal. 3D Euler Spirals for 3D Curve Completion
  • Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen. Orthogonal Range Reporting: Query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
  • Abdul Basit, Nabil Mustafa, Saurabh Ray and Sarfraz Raza. Improving the First Selection Lemma in $\Re3$
  • Bernard Chazelle. A Geometric Approach to Collective Motion
  • Bernard Chazelle. The Geometry of Flocking
  • Pankaj Agarwal, Boris Aronov, Marc van Kreveld, Maarten Löffler and Rodrigo Silveira. Computing Similarity between Piecewise-Linear Functions
  • Jean-Daniel Boissonnat and Arijit Ghosh. Manifold Reconstruction using Tangential Delaunay Complexes
  • Pankaj K. Agarwal. An Improved Algorithm for Computing the Volume of the Union of Cubes
  • William Harvey, Yusu Wang and Rephael Wenger. A Randomized $O(m\log m)$ Time Algorithm for Computing Reeb Graphs of Arbitrary Simplicial Complexes
  • Omid Amini, Jean-Daniel Boissonnat and Pooran Memari. Geometric Tomography With Topological Guarantees
  • Lars Arge, Morten Revsbaek and Norbert Zeh. I/O-efficient computation of water flow across a terrain
  • Timothy M. Chan. Optimal Partition Trees
  • Afra Zomorodian. The Tidy Set: Minimal Simplicial Set for Computing Homology of Clique Complexes
  • Umut Acar, Andrew Cotter, Benoit Hudson and Duru Türkoğlu. Dynamic Well-Spaced Point Sets
  • David Mount and Eunhui Park. A Dynamic Data Structure for Approximate Range Searching
  • Janos Pach, Andrew Suk and Miroslav Treml. Tangencies between families of disjoint regions in the plane


  1. Oops, thanks for fixing it.

  2. Topological inference via meshing here.

  3. http://valis.cs.uiuc.edu/~sariel/papers/09/sspd/
    Thanks... --Sariel

  4. Here's the link to the paper by Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen:


  5. Timothy Chan's paper is available at http://www.cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf


Disqus for The Geomblog