Title of article :
Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems
Author/Authors :
Lusine Yepremyan، نويسنده , , James E. Falk، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2005
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.
Keywords :
Delaunay simplices , Delaunay partitions , Global optimization , Vertex enumeration , Facet enumeration , Voronoi diagrams
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research