Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems |
| |
| Affiliation: | 1. Department of Applied Mathematics, The Bucharest University of Economic Studies, Bucharest, Romania;3. Department of Computer, Control and Management Engineering A. Ruberti (DIAG), Sapienza University of Rome, Italy;4. Institut de Statistique, Biostatistique et de Sciences Actuarielles, Université Catholique de Louvain, Voie du Roman Pays 20, Louvain-la-Neuve B 1348, Belgium;1. College of Auditing and Evaluation, Nanjing Audit University, Nanjing 211815, Jiangsu Province, China;2. Foisie Business School, Worcester Polytechnic Institute, Worcester, MA 01609, USA |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
