Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems

Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems

0.00 Avg rating0 Votes
Article ID: iaor20061010
Country: United Kingdom
Volume: 32
Issue: 4
Start Page Number: 793
End Page Number: 812
Publication Date: Apr 2005
Journal: Computers and Operations Research
Authors: ,
Keywords: sets
Abstract:

Using a pair of 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 suggest an application to 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. The dual problem of enumerating all vertices of a polytope P defined as the intersection of a finite number of half-spaces is also addressed and solved by sequentially enumerating vertices of expanding polytopes defined within P. None of our algorithms are affected by degeneracy. Examples and computational results are given.

Reviews

Required fields are marked *. Your email address will not be published.