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.

کلیدواژه ها:

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