On the limited power of linear probes and other optimization oracles

This paper considers the problem of using norm-computations to find a convex polytope P (not necessarily in any sense the smallest one) that contains C (compact convex subset of X, a real vector space). By finding P we mean to produce its vertex-set or, equivalently for our model, the set of hyperplanes determined by P's facets. It is assumed that the usual arithmetic operations in R and the usual vector operations in X are available without cost, so the problem's difficulty is measured solely in terms of the number of calls to the 'oracle' that computes norms. Such probing oracles are currently of widespread interest because of their use in robotics and tomography.