UNC research on medial axis/generalized Voronoi diagram

Robust medial axis computation

Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware

Recommended links

• Jeff Erickson's medial axis page, describing results on the complexity and giving some interesting examples.
• Approximation of Voronoi Diagrams of Triangles in 3D by Marek Teichmann and Seth Teller (1998).
• Voronoi Diagrams of 2D Points and Line Segments by Martin Held.