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