James E. Falk - The George Washington University, Washington DC, USA
Lusine Yepremyan - The George Washington University, Washington DC, USA

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.

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