Happy New Year!

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).

Comments

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

[JeffE]

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.

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?