×

zbMATH — the first resource for mathematics

Inner and outer approximations of polytopes using boxes. (English) Zbl 1044.65016
Die Autoren behandeln im euklidischen Raum \(\mathbb{R}^d\) (der auf ein kartesisches Koordinatensystem bezogen wird) die Innen- und Außenapproximation eines volldimensionalen, beschränkten, konvexen Polytops \({\mathcal P}\) durch volldimensionale Boxen. Boxen sind konvexe Polytope, deren definierende Hyperebenen zu den Koordinatenachsen parallel sind. Das Polytop \({\mathcal P}\) wird durch ein System linearer Ungleichungen gegeben. Eine Innenapproximation von \({\mathcal P}\) erfolgt durch eine Boxenmenge \({\mathcal J}\), eine Außenapproximation durch eine Boxenmenqe \({\mathcal E}\).
Die zentrale Absicht besteht darin, Methoden anzugeben und zu testen, mit denen der bei einer Approximation entstehende Volumenfehler und zugleich die Gesamtzahl der verwendeten Boxen minimiert werden. Es wird versucht, eine gute Ausgewogenheit zwischen diesen gegensätzlichen Forderungen zu erzielen.
Dafür werden insgesamt 7 Approximationsalgorithmen bereitgestellt und damit gemachte Computererfahrungen präsentiert. Die Grundidee besteht darin, ausgehend von einer Startbox rekursiv vorzugehen, die beiden Forderungen möglichst zu trennen und einen Rekursionsraum zu erzeugen. Die Zeitkomplexität der Algorithmen wird nach der Maximalzahl der eingesetzten Hilfsprogramme beurteilt. Die vorgestellten Algorithmen lassen sich modifizieren zur Approximation der Projektion eines Polytops \({\mathcal P}\) auf einen affinen Teilraum des \(\mathbb{R}^d\), der von den ersten \(k\) \((k< d)\) Basisvektoren aufgespannt wird.

MSC:
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52B11 \(n\)-dimensional polytopes
65Y20 Complexity and performance of numerical algorithms
Software:
cdd
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bárány, I.; Füredi, Z., Computing the volume is difficult, Discrete comput. geom., 2, 319-326, (1987) · Zbl 0628.68041
[2] Bemporad, A.; Fukuda, K.; Torrisi, F.D., Convexity recognition of the union of polyhedra, Computational geometry, 18, 141-154, (2001) · Zbl 0976.68163
[3] Büeler, B.; Enge, A.; Fukuda, K., Exact volume computation for convex polytopes: A practical study, () · Zbl 0960.68162
[4] Cohen, J.; Hickey, T., Two algorithms for determining volumes of convex polyhedra, J. ACM, 26, 3, 401-414, (1979) · Zbl 0403.68067
[5] Eaves, B.C.; Freund, R.M., Optimal scaling of balls and polyhedra, Math. programming, 23, 138-147, (1982) · Zbl 0479.90064
[6] Freund, R.M.; Orlin, J.B., On the complexity of four polyhedral set containment problems, Math. programming, 33, 139-145, (1985) · Zbl 0581.90060
[7] Fukuda, K., Polyhedral computation FAQ, Both html and ps versions available from
[8] Fukuda, K., 0.61 (cdd) 0.76 (cdd+) edition, December 1997
[9] ()
[10] Gritzmann, P.; Klee, V., Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces, Math. programming, 59, 163-213, (1993) · Zbl 0784.90076
[11] Gritzmann, P.; Klee, V., On the complexity of some basic problems in computational convexity: I. containment problems, Discrete math., 136, 129-174, (1994) · Zbl 0824.68052
[12] NAG Foundation Toolbox—For Use with MATLAB, 1995
[13] Nesterov, Y.; Nemirovskii, A., Interior-point polynomial algorithms in convex programming, studies in applied mathematics, (1994), SIAM Philadelphia · Zbl 0824.90112
[14] ()
[15] Torrisi, F.D.; Bemporad, A., Discrete-time hybrid modeling and verification, (), 2899-2904
[16] Zhu, B., Approximating convex polyhedra with axis-parallel boxes, Internat. J. comput. geom. appl., 7, 3, 253-267, (1997)
[17] Ziegler, G.M., Lectures on polytopes, (1995), Springer-Verlag Berlin · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.