This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several $#\P$-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is $#\P$-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes $$ V(\overbrace{K_1\ld K_1}^{m_1}, \overbrace{K_2,\dots,K_2}^{m_2},\dots,\overbrace{K_s,\dots,K_s}^{m_s}) $$ of well-presented convex bodies $K_1,\dots,K_s$, where $m_1,\dots,m_s \in \N_0$ and $m_1 \geq n-\psi(n)$ with $\psi(n)=o(\frac{\log n}{\log \log n})$. The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

Article Free Access Share on A polynomial time algorithm for Minkowski reconstruction Authors: Peter Gritzmann Universität Trier, Fb IV, Mathematik, D-54286 Trier, Germany Universität Trier, Fb IV, Mathematik, D-54286 Trier, GermanyView Profile , Alexander Hufnagel Universität Trier, Fb IV, Mathematik, D-54286 Trier, Germany Universität Trier, Fb IV, Mathematik, D-54286 Trier, GermanyView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 1–9https://doi.org/10.1145/220279.220280Online:01 September 1995Publication History 2citation276DownloadsMetricsTotal Citations2Total Downloads276Last 12 Months9Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF