Title: An Optimal Algorithm for Roundness Determination on Convex Polygons
 
Kurt Swanson
Department of Computer Science
Lund University, Box 118 
S-221 00 Lund, Sweden 
Kurt.Swanson@dna.lth.se

D.T. Lee*
Department of Electrical and Computer Engineering 
Northwestern University 
Evanston, IL, 60208 USA
dtlee@ece.nwu.edu

* Supported in part by the National Science Foundation under the 
  Grant No. CCR-8901815.

V.L. Wu
AT&T Bell Laboratories 
2000 N. Naperville Road
Naperville, IL, 60566-7033 USA 
v.l.wu@lucent.com


Abstract:

In tolerancing, the Out-Of-Roundness factor determines the relative 
circularity of planar shapes.  The measurement of concern in this work 
is the Minimum Radial Separation, as recommended by the American 
National Standards Institute (ANSI).  Here we show that the algorithm 
given in Le and Lee runs in \Theta(n^2) time even for convex polygons. 
Furthermore, we present an optimal O(n) time algorithm to compute the 
Minimum Radial Separation of convex polygons, which represents not only 
a factor n improvement over the previously best known algorithm, but 
also a factor of O(\log n) improvement over Le and Lee's conjectured 
complexity for the problem.

Computational Geometry: Theory and Applications, (5,4) Nov. 1995,
pp. 225-235.