Good and Bad Radii of Convex Polygons
Peter Gritzmann, Laurent Habsieger, Victor L. Klee · SIAM Journal on Computing · 1991
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$.