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