Roundness estimation via random sampling

Abstract

We present an efficient probabilistic algorithm to estimate the roundness of a convex object on the plane. The probing model we use, that is, the type of access the algorithm has to the object, was defined by Cole and Yap [CY87], and is related to physical devices employed in computational metrology. This algorithm is not only simple but also very different from and more efficient than previous algorithms for this problem [Swa93, LL91, EFNN89, MSY97]. Our analysis involves proving sharp versions of the planar isoperimetric inequality and using them in conjunction with results from geometric probability.