Delaunay Partitions and Applications

Using two theorems linking Delaunay Partitions and Linear Programming, we develop a method to generate all simplices in a Delaunay Partition of a set of points and show how to solve a piecewise linear non-convex optimization problem. The same method is shown to enumerate all facets of a polytope given as the convex hull of a finite set of points. None of our algorithms are affected by degeneracy. Examples and computational results are given.

Keywords:

Delaunay Simplices , Non-convex Programs , Facet Enumeration , Vertex Enumeration