Author name cluster

Peter Gritzmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

TCS Journal 2002 Journal Article

On the algorithmic inversion of the discrete Radon transform

Peter Gritzmann
Sven de Vries

The present paper deals with the computational complexity of the discrete inverse problem of reconstructing finite point sets and more general functionals with finite support that are accessible only through some of the values of their discrete Radon transform. It turns out that this task behaves quite differently from its well-studied companion problem involving 1-dimensional X-rays. Concentrating on the case of coordinate hyperplanes in R d and on functionals ψ: Z d→D with D∈{{0, 1, …, r}, N 0} for some arbitrary but fixed r, we show in particular that the problem can be solved in polynomial time if information is available for m such hyperplanes when m⩽d−1 but is NP -hard for m=d and D={0, 1, …, r}. However, for D=N 0, a case that is relevant in the context of contingency tables, the problem is still in P. Similar results are given for the task of determining the uniqueness of a given solution and for a related counting problem.

Details DOI

FOCS Conference 1998 Conference Paper

Approximation of Diameters: Randomization Doesn't Help

Andreas Brieden
Peter Gritzmann
Ravindran Kannan
Victor Klee
László Lovász 0001
Miklós Simonovits

We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximization of the norm over K. In addition to these results for Euclidean spaces, we give tight results for the error of deterministic polynomial-time approximations of radii and norm-maxima for convex bodies in finite-dimensional l/sub p/ spaces.

Details