Testing the Quality ofManufactured Disks and Balls

We consider the problem of testing the roundness of manufactured disks and balls using the finger probing model of Cole and Yap. The running time of our procedures depends on the quality of the object being considered. Quality is a parameter that is negative when the object is not sufficiently round and positive when it is. Quality values close to zero represent objects that are close to the boundary between sufficiently round and insufficiently round. When the object being tested is a disk and its center is known, we describe a procedure that uses O(n) probes and O(n) computation time. (Here n =| 1/q|, where q is the quality of the object.) When the center of the object is not known, a procedure using O(n) probes and O(n log n) computation time is described. When the object is a ball, we describe a procedure that requires O(n ²) probes and O(n ⁴) computation time. Lower bounds are also given that show that these procedures are optimal in terms of the number of probes used. These results extend previous results in two directions by relaxing some of the assumptions required by previous results and by extending these results for three‐dimensional objects.