Polytope Containment and Determination by Linear Probes
Peter Gritzmann, Victor L. Klee, John Westwater · Proceedings of the London Mathematical Society · 1995
As the terms are used here, a body in Rd is 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 C 0 d . A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C 0 d is the function Oc which, 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 Rd are 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.