Carleton University
Technical Report TR-98-08
October 1998
TR-98-08: Testing the Quality of Manufactured Balls
Prosenjit Bose & Pat Morin
Abstract
We consider the problem of testing the roundness of a manufactured ball, using the finger probing model of Cole and Yap \cite{cy87}. When the center of the object is known, a procedure requiring $O(n^2)$ probes and $O(n^2)$ computation time is described. (Here $n=|1/q|$, where $q$ is the quality of the object.) When the center of the object is not known, the procedure requires $O(n^2)$ probes and $O(n^4)$ computation time. We also give lower bounds which show that the number of probes used by these procedures is optimal.