Polytope containment and determination by linear probes

As the terms are used here, a body in R^dis 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 ϐ^d₀. A set X is symmetric if X = â–X. The ray-oracle of a body Cεϐ^d₀is the function O_cwhich, 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 R^dare 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.