scientific article; zbMATH DE number 1182920

Publication date 11 February 2001

computational complexity convex bodies presentations of polytopes qualitative matrices

Mixed volumes and related topics in convex geometry (52A39) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Linear programming (90C05)

Review text

This chapter is part of a larger collection of state-of-the-art surveys in Discrete and Computational Geometry. It deals with computational issues in convexity theory. Most of the problems mentioned here concern arbitrary-dimensional bodies, and the complexity results sought depend both on \(m\) (the complexity of the convex body) and \(n\) (the dimension of the ambient space). Other related chapters of the same book include Chapter 7 (Lattice Points and Lattice Polytopes), Chapter 13 (Basic Properties of Convex Polytopes), Chapter 15 (Face Numbers of Polytopes and Complexes), and Chapter 19 (Convex Hull Computations). Most of the results of the first part are related to Linear Programming and Combinatorial Optimization [explained in the book by \textit{M. Grötschel, L. Lovász}, and \textit{A. Shrijver}, ``Geometric Algorithms and Combinatorial Optimization, Springer (1988; Zbl 0634.05001)]. In particular, one of the main problems discussed in the first section is the conversion between the vertex representation and its dual facet representation. It is a well-known result of McMullen and Shephard [{see \textit{P. McMullen, G. C. Shephard, J. E. Reeve}, and \textit{A. A. Ball}, ``Convex Polytopes and the Upper Bound Conjecture, Cambridge Univ. Press (1971; Zbl 0217.46702)] that if \(m\) represents the number of vertices (resp. facets), then the number of facets (resp. vertices) is at most \[ \mu(n,m) = \left( { m - \lfloor (n+1)/2 \rfloor \atop m-n } \right) + \left( { m - \lfloor (n+2)/2) \rfloor \atop m-n } \right), \] which is \(O(m^{\lfloor n/2 \rfloor})\) when the dimension \(n\) is fixed and \(m\) is arbitrarily large, a result well used in computational geometry. Other representation issues discussed include algorithmic convexity theory (where the convex body is presented by a membership oracle). There are efficient oracles for vertex-presented and facet-presented polytopes, as well as for segment-presented zonotopes (Minkowski sums of a set of segments). On the other hand, some of the hardship results (e.g. the impossibility of computing the exact volume in time polynomial in \(n\)) for general convex bodies in the oracle model \textit{do not} hold for those facet- or vertex-presented polytopes. While the first part dealt with the representation issues (sections 27.1 and 27.2), in a second part themes related to computation and applications are discussed under the headers Volume Computations (27.3), Mixed Volumes (27.4), Containment Problems (27.5) and Radii (27.6), and a last chapter tackles the problem of mathematical modeling of practical problems with Interval Matrices and Qualitative Matrices (27.7). Most of these results are too involved to explain here, but some key words may help to orient the reader: Computing the volume of a convex set exactly is hard, but randomized approximation algorithms exist (27.3), Brunn-Minkowski Inequality (27.5), and its application to counting and/or computing isolated solutions of sparse polynomial systems (Newton polytopes), Löwner-John ellipsoids (27.5), inner and outer radius, diameter, and width (27.6), sign-solvability of an interval matrix is not known to be in P or not (27.7).} For the entire collection see [Zbl 0890.52001].

Recommendations

Cited in

(10)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4401017)