POLYTOPE CONTAINMENT AND DETERMINATION BY LINEAR PROBES

As the terms are used here, a body in R(d) is a compact convex set wit h non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes t he origin 0 is denoted by C-0(d). A set X is symmetric if X = -X. The ray-oracle of a body C is an element of C-0(d) is the function O-C whi ch, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerne d with a few central aspects of the following general question: given certain information about C, what additional information can be obtain ed by questioning the ray-oracle, and how efficiently can it be obtain ed? It is assumed that infinite-precision real arithmetic and the usua l vector operations in R(d) are available at no cost, so the efficienc y of an algorithm is measured solely in terms of its number of calls t o the ray-oracle. The paper discusses two main problems, the first of which-the containment problem-arose from a question in abstract numeri cal analysis. Here the goal is to construct a polytope P (not necessar ily in any sense a small one) that contains C, where this requires pre cise 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 asym metric, but the main result on the containment problem is negative, It asserts that when d greater than or equal to 3 and the body is known only to be rotund and symmetric, there is no algorithm for the contain ment problem, This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the r ay-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment prob lem admits an algorithmic solution based solely on the ray-oracle: con struct 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 an d the problem is to construct C with the aid of a finite number of cal ls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the 'combinatorial compl exity') of C.