How good are convex hull algorithms?
| Autor: | David Avis, Raimund Seidel, David Bremner |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Convex hull
medicine.medical_specialty Control and Optimization Convex hull algorithms Polyhedral combinatorics 0211 other engineering and technologies Convex set Polytope 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Convex hulls Convex polytope medicine Mathematics::Metric Geometry Polytope model Mathematics Discrete mathematics 021103 operations research Triangulation complexity Vertex enumeration Lattice complexity Computer Science Applications Computational Mathematics Convex polytopes Computational Theory and Mathematics 010201 computation theory & mathematics Geometry and Topology Vertex enumeration problem |
| Zdroj: | Computational Geometry. 7(5-6):265-301 |
| ISSN: | 0925-7721 |
| DOI: | 10.1016/s0925-7721(96)00023-5 |
| Popis: | A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is to compute V from H>. The facet enumeration problem is to compute H from V. These two problems are essentially equivalent under point/hyperplane duality. They are among the central computational problems in the theory of polytopes. It is open whether they can be solved in time polynomial in | H | + | V | and the dimension. In this paper we consider the main known classes of algorithms for solving these problems. We argue that they all have at least one of two weaknesses: inability to deal well with “degeneracies”, or, inability to control the sizes of intermediate results. We then introduce families of polytopes that exercise those weaknesses. Roughly speaking, fat-lattice or intricate polytopes cause algorithms with bad degeneracy handling to perform badly; dwarfed polytopes cause algorithms with bad intermediate size control to perform badly. We also present computational experience with trying to solve these problem on these hard polytopes, using various implementations of the main algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect