Efficient Proximity Probing Algorithms for Metrology

摘要

Metrology, the theoretical and practical study of measurement, has applications in automated manufacturing, inspection, robotics, surveying, and healthcare. The geometric probing problem considers how to optimally use a probe to measure geometric properties. In this paper, we consider a proximity probe which, given a point, returns the distance to the boundary of the nearest object. When there is an unknown convex polygon in the plane, the goal is to minimize the number of probe measurement needed to exactly determine the shape and location of . We present an algorithm with upper bound of probes, where is the number of vertices and is the number of acute angles of . The algorithm requires constant time per probe, and hence, time to determine . We also address the related problem where the unknown polygon is a member of a known finite set and the goal is to efficiently determine which polygon is present. When is the size of and is the maximum number of vertices of any member of , we present an algorithm with an upper bound of