Accepted ACM SoCG Papers and Videos

ACM SoCG 2012 Accepted Papers and Videos

(papers in random order)

Andrew Suk. Disjoint edges in complete topological graphs
Marek Elias and Jiri Matousek. Higher-order Erdos–Szekeres theorems
Natan Rubin. On topological changes in the Delaunay triangulation of moving points
Joseph M. Burdis and Irina A. Kogan. Object-image correspondence for curves under central and parallel  projections
Alina Ene, Sariel Har-Peled and Benjamin Raichel. Geometric Packing under Non-uniform Constraints
Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand, Nicolai Hähnle and Martin Niemeier. On sub-determinants and the diameter of polyhedra
Jens M. Schmidt and Pavel Valtr. Cubic Plane Graphs on a Given Point Set
Micha Sharir, Adam Sheffer and Emo Welzl. Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn’s Technique
Therese Biedl and Martin Vatshelle. The point-set embeddability problem for plane graphs
Abhijin Adiga and Sunil Chandran. Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions
Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour and Anastasios Sidiropoulos. How to Walk Your Dog in the Mountains with No Magic Leash
Herbert Edelsbrunner, Brittany Terese Fasy and Günter Rote. Add Isotropic Gaussian Kernels at Own Risk: More and More Resiliant Modes in Higher Dimensions
Kenneth Clarkson, Wolfgang Mulzer and C. Seshadhri. Self-improving Algorithms for Coordinate-wise Maxima
Don Sheehy. Linear-Size Approximations to the Vietoris-Rips Filtration
Herbert Edelsbrunner and Michael Kerber. Alexander Duality for Functions: the Persistent Behavior of Land and Water and Shore
Wolfgang Mulzer and Daniel Werner. Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Eric Colin De Verdière, Grégory Ginot and Xavier Goaoc. Multinerves and Helly numbers of acyclic families
Guillermo D. Canas and Steven Gortler. Duals of Orphan-Free Anisotropic Voronoi Diagrams are Triangulations
Gert Vegter, Chee Yap and Amit Chattopadhyay. Certified Computation of planar Morse-Smale Complexes
Jeff Erickson and Amir Nayyeri. Tracing Compressed Curves in Triangulated Surfaces
Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen Kobourov and Torsten Ueckerdt. Computing Cartograms with Optimal Complexity
Michal Adamaszek and Juraj Stacho. Algorithmic complexity of finding cross-cycles in flag complexes
Yufei Tao. Stabbing Horizontal Segments with Vertical Rays
Anne Driemel, Sariel Har-Peled and Benjamin Raichel. On the Expected Complexity of Voronoi Diagrams on Terrains
Ashwinkumar Badanidiyuru, Robert Kleinberg and Hooyeon Lee. Approximating Low-Dimensional Coverage Problems
Silvia Fernandez, Bernardo M. Abrego, Oswin Aichholzer, Pedro Ramos and Gelasio Salazar. The 2-page crossing number of $K_{n}$
Peyman Afshani, Lars Arge and Kasper Green Larsen. Higher-dimensional Orthogonal Range Reporting and Rectangle Stabbing in the Pointer Machine Model
Kasper Green Larsen and Huy L. Nguyen. Improved Range Searching Lower Bounds
Jean-Daniel Boissonnat, Ramsay Dyer and Arijit Ghosh. Stability of Delaunay-type structures for manifolds
Siu-Wing Cheng, Jiongxin Jin and Man-Kit Lau. A Fast and Simple Surface Reconstruction Algorithm
Nabil Mustafa and Saurabh Ray. A theorem of Barany revisited and extended
Éric Colin De Verdière and Arnaud De Mesmay. Testing graph isotopy on surfaces
Saurabh Ray, Victor Alvarez, Karl Bringmann and Radu Curticapean. Counting Crossing Free Structures
Peyman Afshani. Improved Pointer Machine and I/O Lower Bounds for Simplex Range Reporting and Related Problems
Salman Parsa. A Deterministic O(m log m) Time Algorithm for the Reeb Graph
Haim Kaplan and Micha Sharir. Finding the Maximal Empty Disk Containing a Query Point
Sunil Arya, Guilherme D. Da Fonseca and David Mount. Optimal Area-Sensitive Bounds for Polytope Approximation
Ioannis Emiris, Vissarion Fisikopoulos, Christos Konaxis and Luis Peñaranda. An output-sensitive algorithm for computing projections of resultant polytopes
Timothy M. Chan. Conflict-Free Coloring of Points with Respect to Rectangles and Approximation Algorithms for Discrete Independent Set
Anna Gundert and Uli Wagner. On Laplacians of Random Complexes
Hakan Yıldız and Subhash Suri. On Klee’s Measure Problem on Grounded Boxes
Ciprian Borcea, Ileana Streinu and Shin-Ichi Tanigawa. Periodic body-and-bar frameworks
Janos Pach and Jacob Fox. String graphs and incomparability graphs
Amirali Abdullah, John Moeller and Suresh Venkatasubramanian. Approximate Bregman near neighbors in sublinear time: Beyond the triangle inequality

Videos

The videos and links to accompanying material can be found at http://www.computational-geometry.org/SoCG-videos/socg12video/

====
Configuration Space Visualization
Dror Atariah; Günter Rote
====
Surface Patches from Unorganized Space Curves
Fatemeh Abbasinejad; Pushkar Joshi; Nina Amenta
====
Lang’s Universal Molecule Algorithm
John C. Bowers; Ileana Streinu
====
The Sticky Geometry of the Cosmic Web
Johan Hidding; Rien van de Weygaert; Gert Vegter; Bernard J.T. Jones; Monique Teillaud