Complexity of Delaunay Triangulation

Annamaria Amenta
University of California, Davis (UC Davis)

Delaunay triangulations are the projections of convex polytopes. In recent years much has been learned about the the complexity of Delaunay triangulations as function of the distribution of their vertices. How much of this can be applied to polytopes in general? We review the results and the open questions.

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?