We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximization of the norm over K. In addition to these results for Euclidean spaces, we give tight results for the error of deterministic polynomial-time approximations of radii and norm-maxima for convex bodies in finite-dimensional l/sub p/ spaces.

The “radii” considered here are the inradius $\rho $, the circumradius R, the diameter $\delta $, and the width $\Delta $. The convex polygons in question have their vertices at points of the integer lattice in $\mathbb{R}^2 $, and their radii are measured with respect to an $\ell ^p $ norm. Computation of these radii for convex polygons (and of their higher-dimensional analogues for convex polytopes) is of interest in connection with a number of applications, and may be regarded as a basic problem in computational geometry. The terms good radius and bad radius refer to the existence or nonexistence of a rationalizing polynomial—a nonconstant rational polynomial q such that $q(\varphi (C))$ is rational whenever C is a convex lattice polygon and $\varphi $ is the radius function in question. When a radius is good, the polynomial is a tool for implicit computation of the radius in the binary model of computation; otherwise it seems to be necessary to resort to approximation. It is proved here that all four radii are good when $p \in \{ 1,\infty \} $, while $\delta $ is good when p is an integer and $\Delta $ is good when $p / (p - 1)$ is an integer. Thus $\delta $ and $\Delta $ are both good when $p = 2$, and it turns out that R is also good in this case. However, the main results are that r is bad when $p = 2$ and R is bad for each integer $p \geq 3$.

Article Free AccessOn the limited power of linear probes and other optimization oracles Authors: Peter Gritzmann Universität Augsburg, Institut für Mathematik, Universitätsstr. 8, D-8900 Augsburg, Federal Republic of Germany Universität Augsburg, Institut für Mathematik, Universitätsstr. 8, D-8900 Augsburg, Federal Republic of GermanyView Profile , Victor Klee Department of Mathematics, University of Washington, Seattle, Washington Department of Mathematics, University of Washington, Seattle, WashingtonView Profile , John Westwater Department of Mathematics, University of Washington, Seattle, Washington Department of Mathematics, University of Washington, Seattle, WashingtonView Profile Authors Info & Claims SCG '90: Proceedings of the sixth annual symposium on Computational geometryMay 1990 Pages 92–101https://doi.org/10.1145/98524.98544Published:01 May 1990Publication History 1citation10DownloadsMetricsTotal Citations1Total Downloads10Last 12 Months3Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A d -dimensional circuit code of spread s (also called SIB s , code or circuit code of minimum distance s ) is a simple circuit Q in the graph of the d -dimensional cube [0, 1] d such that any two vertices of Q differing in exactly r coordinates, with r < s , can be joined by a path formed from r edges of Q . Such codes are designed to introduce error detection into certain analog-to-digital conversion systems. Longer codes correspond to increased accuracy of the system, and hence there is interest in determining the maximum length C ( d , s ) of d -dimensional circuit codes of spread s . In the present study the author contributes to this problem for even values of s by describing a method of combining a code of spread s with a suitably related code of spread s -1 so as to produce a longer code of spread s .