An efficient proximity probing algorithm for metrology

摘要

Metrology, the theoretical and practical study of measurement, has applications in automated manufacturing, inspection, robotics, surveying, and healthcare. An important problem within metrology is how to interactively use a measuring device, or probe, to determine some geometric property of an unknown object; this problem is known as geometric probing. In this paper, we study a type of proximity probe which, given a point, returns the distance to the boundary of the object in question. We consider the case where the object is a convex polygon P in the plane, and the goal of the algorithm is to minimize the upper bound on the number of measurements necessary to exactly determine P. We show an algorithm which has an upper bound of 3.5n + k + 2 measurements necessary, where n is the number of vertices and k ≤ 3 is the number of acute angles of P. Furthermore, we show that our algorithm requires O(1) computations per probe, and hence O(n) time to determine P.