Algorithmic problems in Brunn-Minkowski theory.

*(English)*Zbl 0847.52012
Trier: Univ., FB 4, 153 p. (1995).

This thesis is an extensive study of the computational complexity of several questions on convex polytopes or more general convex bodies, arising from Brunn-Minkowski theory. Main topics are volumes of Minkowski sums, the computation of mixed volumes, and Minkowski’s existence (or reconstruction) problem. The binary Turing machine model of computation is employed (thus rational inputs and outputs are required), and polytopes occur either as \({\mathcal V}\)-presentations (convex hulls of vertices) or \({\mathcal H}\)-presentations (intersections of halfspaces). For general convex bodies, different oracle concepts are used. Since it is known that computing the volume of a polytope given by an \({\mathcal H}\)- or by a \({\mathcal V}\)-presentation is \(\# \mathbb{P}\)-hard, one expects similar results for mixed volumes. The following are examples of the results obtained. Computing the volume of a zonotope generated by rational vectors is \(\# \mathbb{P}\)-hard. Approximately computing the volume of the Minkowski sum of ellipsoids is \(\# \mathbb{P}\)-hard. Computing the mixed volume of \(n\) (axes-parallel) boxes of dimension \(n\) with rational edge length is \(\# \mathbb{P}\)-hard. There are also corresponding easiness results for mixed volume computation. A further problem treated is how efficiently mixed volumes can be approximated in fixed dimension by means of deterministic algorithms. For variable dimension, under suitable restrictions, polynomial-time randomized algorithms for the relative approximation of (“few”) mixed volumes of well-presented convex bodies with given error are described.

Minkowski’s existence theorem for polytopes with given normals and volumes of facets is treated in the following adaptation to the model of computation, called MinkApp: [Instance: \(m,n \in \mathbb{N}\); vectors \(a_1, \dots, a_m \in \mathbb{Q}^n \backslash \{0\}\), mutually noncollinear, which span \(\mathbb{R}^n\); a positive rational vector \(v = (\nu_1, \dots, \nu_m)\) such that \(\sum^m_{i = 1} \nu_i a_i = 0\); a positive rational error bound \(\varepsilon\). Task: Determine a rational vector \(\widetilde b = (\widetilde \beta_1, \dots, \widetilde \beta_m )^T\) such that the facet volumes \(\widetilde \mu_1, \dots, \widetilde \mu_m\) of the polytope \[ \widetilde P = \bigl\{ x \in \mathbb{R}^n : \langle a_i, x \rangle \leq \widetilde \beta_i, \quad \text{for} \quad 1 = 1,2, \dots, m \bigr\} \] satisfy \(\max_{i = 1,\dots, m} \bigl |\widetilde \mu_i - \nu_i |a_i |\bigr |< \varepsilon.]\) If the dimension \(n\) is fixed, the corresponding problem is called \(n\)-MinkApp, and the exact version \((\varepsilon = 0)\) is MinkRecon. The problem MinkRecon is equivalent to a certain convex program (as already used by Minkowski). Approximating the solution of MinkRecon, using stability results, plays an important role. The following are the principal results obtained. For each fixed \(n\in\mathbb{N}\), \(n\)-MinkApp can be solved in polynomial time. MinkApp can be solved in polynomial time whenever an oracle for approximating the volume of \({\mathcal H}\)-polytopes is available. The problem MinkApp is \(\# \mathbb{P}\)-hard and \(\# \mathbb{P}\)-easy.

Minkowski’s existence theorem for polytopes with given normals and volumes of facets is treated in the following adaptation to the model of computation, called MinkApp: [Instance: \(m,n \in \mathbb{N}\); vectors \(a_1, \dots, a_m \in \mathbb{Q}^n \backslash \{0\}\), mutually noncollinear, which span \(\mathbb{R}^n\); a positive rational vector \(v = (\nu_1, \dots, \nu_m)\) such that \(\sum^m_{i = 1} \nu_i a_i = 0\); a positive rational error bound \(\varepsilon\). Task: Determine a rational vector \(\widetilde b = (\widetilde \beta_1, \dots, \widetilde \beta_m )^T\) such that the facet volumes \(\widetilde \mu_1, \dots, \widetilde \mu_m\) of the polytope \[ \widetilde P = \bigl\{ x \in \mathbb{R}^n : \langle a_i, x \rangle \leq \widetilde \beta_i, \quad \text{for} \quad 1 = 1,2, \dots, m \bigr\} \] satisfy \(\max_{i = 1,\dots, m} \bigl |\widetilde \mu_i - \nu_i |a_i |\bigr |< \varepsilon.]\) If the dimension \(n\) is fixed, the corresponding problem is called \(n\)-MinkApp, and the exact version \((\varepsilon = 0)\) is MinkRecon. The problem MinkRecon is equivalent to a certain convex program (as already used by Minkowski). Approximating the solution of MinkRecon, using stability results, plays an important role. The following are the principal results obtained. For each fixed \(n\in\mathbb{N}\), \(n\)-MinkApp can be solved in polynomial time. MinkApp can be solved in polynomial time whenever an oracle for approximating the volume of \({\mathcal H}\)-polytopes is available. The problem MinkApp is \(\# \mathbb{P}\)-hard and \(\# \mathbb{P}\)-easy.

Reviewer: R.Schneider (Freiburg i.Br.)

##### MSC:

52B55 | Computational aspects related to convexity |

68Q25 | Analysis of algorithms and problem complexity |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |