%0 Journal Article %1 Gritzmann_Hufnagel_1999 %A Gritzmann, P. %A Hufnagel, A. %D 1999 %I Oxford University Press - London Mathematical Society %J Journal of the London Mathematical Society %K minkowski %N 3 %P 1081-1100 %R 10.1112/S0024610799007413 %T On the Algorithmic Complexity of Minkowskis Reconstruction Theorem %V 59 %X In 1903 Minkowski showed that, given pairwise different unit vectors μ1, …, μm in Euclidean n-space Rn which span Rn, and positive reals μ1, …, μm such that ∑mi=1μiμi = 0, there exists a polytope P in Rn, unique up to translation, with outer unit facet normals μ1, …, μm and corresponding facet volumes μ1, …, μm. This paper deals with the computational complexity of the underlying reconstruction problem, to determine a presentation of P as the intersection of its facet halfspaces. After a natural reformulation that reflects the fact that the binary Turing-machine model of computation is employed, it is shown that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is #P-hard when the dimension is part of the input. The problem of ‘Minkowski reconstruction’ has various applications in image processing, and the underlying data structure is relevant for other algorithmic questions in computational convexity.

@article{Gritzmann_Hufnagel_1999, abstract = {In 1903 Minkowski showed that, given pairwise different unit vectors μ1, …, μm in Euclidean n-space Rn which span Rn, and positive reals μ1, …, μm such that ∑mi=1μiμi = 0, there exists a polytope P in Rn, unique up to translation, with outer unit facet normals μ1, …, μm and corresponding facet volumes μ1, …, μm. This paper deals with the computational complexity of the underlying reconstruction problem, to determine a presentation of P as the intersection of its facet halfspaces. After a natural reformulation that reflects the fact that the binary Turing-machine model of computation is employed, it is shown that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is #P-hard when the dimension is part of the input. The problem of ‘Minkowski reconstruction’ has various applications in image processing, and the underlying data structure is relevant for other algorithmic questions in computational convexity.}, added-at = {2013-10-25T03:51:52.000+0200}, author = {Gritzmann, P. and Hufnagel, A.}, biburl = {https://www.bibsonomy.org/bibtex/24fadc8636ef7306eb360067d4e26fff8/ytyoun}, doi = {10.1112/S0024610799007413}, interhash = {133cddd85f364bd118e857fb5b9be71f}, intrahash = {4fadc8636ef7306eb360067d4e26fff8}, journal = {Journal of the London Mathematical Society}, keywords = {minkowski}, month = jun, number = 3, pages = {1081-1100}, publisher = {Oxford University Press - London Mathematical Society}, timestamp = {2013-10-25T03:51:52.000+0200}, title = {On the Algorithmic Complexity of Minkowskis Reconstruction Theorem}, volume = 59, year = 1999 }