Polytope containment and determination by linear probes

Peter Gritzmann, Victor Klee, John Westwater

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


As the terms are used here, a body in Rdis a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by ϐd0. A set X is symmetric if X = â–X. The ray-oracle of a body Cεϐd0is the function Ocwhich, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rdare available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which-the containment problem–arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ≥ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem–the reconstruction problem– it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ’combinatorial complexity–) of C.

Original languageEnglish
Pages (from-to)691-720
Number of pages30
JournalProceedings of the London Mathematical Society
Issue number3
StatePublished - May 1995
Externally publishedYes


Dive into the research topics of 'Polytope containment and determination by linear probes'. Together they form a unique fingerprint.

Cite this