Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Efficient proximity probing algorithms for metrology

Published Web Location
No data is associated with this publication.

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 Γ).

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item