UC Berkeley

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 P in the plane, the goal is to minimize the number of probe measurement needed to exactly determine the shape and location of P. We present an algorithm with upper bound of 3.5n + k + 2 probes, where n is the number of vertices and k ≤ 3 is the number of acute angles of P. The algorithm requires constant time per probe, and hence, O(n) time to determine P. 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 m is the size of Γ and n′ is the maximum number of vertices of any member of Γ, we present an algorithm with an upper bound of 2n + 2 probes with O(1) computations per probe and a O(n′m) preprocessing phase (depending only on Γ).