Name
Abstract | ||
|---|---|---|
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(√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 lp spaces |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/SFCS.1998.743451 | Palo Alto, CA |
Keywords | Field | DocType |
computational geometry,deterministic algorithms,optimisation,polynomial approximation,Euclidean n-space,Euclidean spaces,deterministic polynomial-time algorithm,deterministic polynomial-time approximations,diameters approximation,lower bounds,polynomial-time algorithm,upper bounds | Discrete mathematics,Approximation algorithm,Combinatorics,Convex body,Nondeterministic algorithm,Upper and lower bounds,Polynomial remainder theorem,Circumscribed circle,Regular polygon,Mathematics,Euclidean shortest path | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-8186-9172-7 | 16 |
PageRank | References | Authors |
1.35 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brieden, A. | 1 | 16 | 1.35 |
| Gritzmann, P. | 2 | 16 | 1.35 |
| Ravindran Kannan | 3 | 3893 | 850.76 |
| Victor Klee | 4 | 169 | 17.23 |