Name
Abstract | ||
|---|---|---|
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 R2, and their radii are measured with respect to an lp 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(phi-(C)) is rational whenever C is a convex lattice polygon and phi 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 is-an-element-of {1, infinity}, 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 greater-than-or-equal-to 3. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1137/0220024 | SIAM J. Comput. |
Keywords | Field | DocType |
bad radius,convex polygon,circumradius,polarity,inradius,diameter,algebraic number,width | Discrete mathematics,Polygon,Combinatorics,Algebraic number,Vertex (geometry),Radius,Circumscribed circle,Regular polygon,Polytope,Integer lattice,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 2 | 0097-5397 |
Citations | PageRank | References |
5 | 1.60 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Gritzmann | 1 | 412 | 46.93 |
| Laurent Habsieger | 2 | 58 | 13.44 |
| Victor Klee | 3 | 169 | 17.23 |