About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1999
Conference paper
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.