Name
Title | ||
|---|---|---|
Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems |
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.cor.2003.08.018 | Computers & OR |
Keywords | DocType | Volume |
Delaunay partitions,dual problem,convex hull,polytope P,Delaunay simplices,linear programming,Voronoi diagrams,Facet enumeration,finite set,facet enumeration problem,computational result,finite number,Vertex enumeration,piecewise linear non-convex optimization,sequentially enumerating vertex,Delaunay partition,Global optimization | Journal | 32 |
Issue | ISSN | Citations |
4 | Computers and Operations Research | 3 |
PageRank | References | Authors |
0.60 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lusine Yepremyan | 1 | 3 | 0.60 |
| James E. Falk | 2 | 297 | 68.47 |