LARGE CONVEX-HULL PROBLEMS

Authors
AVIS D BREMNER D
Citation
D. Avis et D. Bremner, LARGE CONVEX-HULL PROBLEMS, Zeitschrift fur angewandte Mathematik und Mechanik, 76, 1996, pp. 179-182
Citations number
16
Categorie Soggetti
Mathematics,"Mathematical Method, Physical Science",Mechanics,Mathematics
Journal title
Zeitschrift fur angewandte Mathematik und Mechanik → ACNP
ISSN journal
00442267
Volume
76
Year of publication
1996
Supplement
3
Pages
179 - 182
Database
ISI
SICI code
0044-2267(1996)76:<179:LCP>2.0.ZU;2-2
Abstract
Every convex polytope has both a vertex and a halfspace description. T he complexity of translating from the vertices to the halfspaces (conv ex hull) or vice versa (vertex enumeration) remains an important open problem in computational geometry. In this note we present families of hard polytopes for algorithms using pivoting, constraint insertion, a nd triangulation, and discuss techniques for estimating the difficulty of a convex hull or vertex enumeration instance.