It's been a good couple of months for computational geometry.

- Nir Ailon* and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. (Well, the slides look cool, anyway.)
- Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel Smid. Data structures for halfplane proximity queries and incremental Voronoi diagrams.
- Ken Clarkson. Building triangulations using ε-nets.
- Hervé Fournier and Antoine Vigneron. Lower bounds for geometric diameter problems [pdf].
- Jonathan Kelner* and Daniel Speilman. A randomized polynomial-time simplex algorithm for linear programming. (Thanks Lance!)
- Vladlen Koltun. The arrangement method for linear programming [pdf].
- Wolfgang Mulzer* and Günter Rote. Minimum-weight triangulation is NP-hard. (Thanks David and Suresh!)

*Marked authors are, as far as I know, still PhD students. Apologies to anyone insulted by their omission (or inclusion).

Does Koltun prove a strongly polynomial linear feasiblity algorithm? Or is he just sketching out an approach?

Posted by: | January 05, 2006 at 11:42 PM

He's really just sketching a promising variant of the simplex algorithm. Simplex (in its simplest form) can be described as a guided walk along the edges of the feasible polyhedron. Vladlen's algorithm uses a different graph—the arrangement of the constraint hyperplanes—which provably has only polynomial diameter. Polytope graphs are believed to have small diameter [http://www.math.ethz.ch/~feichtne/ATDM/semi04winter/node11.html], but but the lack of proof is commonly cited as a bottleneck in finding a strongly-polynomial simplex algorithm. Vladlen's result removes that bottleneck.

Posted by: JeffE | January 06, 2006 at 03:49 PM

Ok. So what happened with Koltun? Did he just give up on this strongly polynomial simplex pivot-scheme? Or did he want to claim credit for the arrangement idea and is trolling for collaborators to finish the job? Or does he want two papers out of this little fest?

Posted by: | January 09, 2006 at 11:46 PM