Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-12-01T01:08:40.220Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE ALGORITHMIC COMPLEXITY OF MINKOWSKI'S RECONSTRUCTION THEOREM

Published online by Cambridge University Press:  01 June 1999

PETER GRITZMANN  and
ALEXANDER HUFNAGEL
PETER GRITZMANN
Affiliation:
Technische Universität München, Zentrum Mathematik, D-80290 München, Germany, [email protected]
ALEXANDER HUFNAGEL
Affiliation:
Spinnereistraße 10, D-91052 Erlangen, Germany
Get access

Abstract

In 1903 Minkowski showed that, given pairwise different unit vectors μ1, …, μm in Euclidean n-space ℝn which span ℝn, and positive reals μ1, …, μm such that [sum ]mi=1μiμi = 0, there exists a polytope P in ℝn, 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 #ℙ-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.

Type
Notes and Papers
Information
Journal of the London Mathematical Society , Volume 59 , Issue 3 , June 1999 , pp. 1081 - 1100
Copyright
The London Mathematical Society 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)