Here's a selection of computational geometry and topology papers accepted to SODA 2012. As usual, this list is neither exclusive nor exhaustive; for many papers, I'm just guessing about the content from the title and/or authors.
Geometry
Yes, most data structure papers count.
- The maximum number of faces of the Minkowski sum of two convex polytopes
Menelaos I. Karavelas and Eleni Tzanaki - Physarum Can Compute Shortest Paths
Vincenzo Bonifaci, Kurt Mehlhorn, and Girish Varma - A Near-Linear Algorithm for Projective Clustering Integer Points
Kasturi Varadarajan and Xin Xiao - On a Linear Program for Minimum-Weight Triangulation
Arman Yousefi and Neal Young - Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts
Anne Driemel and Sariel Har-Peled - I/O-Efficient Data Structures for Colored Range and Prefix Reporting
Kasper Green Larsen and Rasmus Pagh - Sparser Johnson-Lindenstrauss Transforms
Daniel Kane and Jelani Nelson - Information Dissemination via Random Walks in d-Dimensional Space
Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang - Fast zeta transforms for point lattices
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen - Partial match queries in random quadtrees
Nicolas Broutin, Ralph Neininger, and Henning Sulzbach - Packing anchored rectangles
Adrian Dumitrescu and Csaba Toth - Confluent Persistence Revisited
Sebastien Collette, John Iacono, and Stefan Langerman - Using Hashing to Solve the Dictionary Problem (In External Memory)
John Iacono and Mihai Patrașcu - Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir - Computing distance between piecewise linear bivariate functions
Boris Aronov and Guillaume Moroz - Algorithms and Data Structures for the Transportation Problem in Geometric Settings
R Sharathkumar and Pankaj Agarwal - Fully Persistent B-trees
Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas - Dimension reduction for finite trees in l_1
James Lee, Arnaud De Mesmay, and Mohammad Moharrami - Bidimensionality and Geometric Graphs
Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh
Topology
Yes, most planar graph papers count.
- Computing all maps into a sphere
Martin Cǎdek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner - Exact Distance Oracles for Planar Graphs
Shay Mozes and Christian Sommer - Spanning closed walks and TSP in 3-connected planar graphs
Ken-Ichi Kawarabayashi and Kenta Ozeki - Approximate Tree Decompositions of Planar Graphs in Linear Time
Frank Kammer and Torsten Tholey - Finding an induced path of given parity in planar graphs in polynomial time
Marcin Kaminski and Naomi Nishimura - Near optimal distance oracle for planar digraphs avoiding a failed node or link
Utkarsh Lath, Surender Baswana, and Anuradha Mehta - Global Minimum Cuts in Surface Embedded Graphs
Jeff Erickson, Kyle Fox, and Amir Nayyeri - The Maximum Degree of Random Planar Graphs
Michael Drmota, Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger - Local Homology Transfer and Stratification Learning
Paul Bendich, Bei Wang, and Sayan Mukherjee
You may want to add the following one to the Geometry list:
Polytope Approximation and the Mahler Volume
Sunil Arya, Guilherme D. da Fonseca, and David Mount
Posted by: Guilherme | September 13, 2011 at 06:06 AM