The first problem, named sensing by inscription, involves determining the pose of a convex n-gon from a set of m supporting cones. An algorithm with running time O(nm) which almost always reduces to O(n + m log n) is presented to solve for all possible poses of the polygon. We prove that the number of possible poses cannot exceed 6n, given m >= 2 supporting cones with distinct vertices. Simulation experiments demonstrate that two supporting cones are sufficient to determine the real pose of the n-gon in most cases. Our results imply that sensing in practice can be carried out by obtaining viewing angles of a planar part at multiple exterior sites in the plane.

On many occasions a parts feeder will have reduced the number of possible poses of a part to a small finite set. Our second problem, named sensing by point sampling, is concerned with a more general version---finding the minimum number of sensing points required to distinguish between n polygonal shapes with a total of m edges. In practice this can be implemented by embedding a series of point light detectors in a feeder tray or by using a set of mechanical probes that touch the feeder at a finite number of predetermined points. We show that this problem is equivalent to an NP-complete set-theoretic problem introduced as Discriminating Set, and present an O(n^2 m^2) approximation algorithm to solve it with a ratio of 2 ln n. Furthermore, we prove that one can use an algorithm for Discriminating Set with ratio c log n to construct an algorithm for Set Covering with ratio c log n + O(log log n). Thus the ratio 2 ln n is asymptotically optimal unless NP \subset DTIME(n^{poly log n}), a consequence of known results on approximating Set Covering. The complexity of subproblems of Discriminating Set is also analyzed, based on their relationship to a generalization of Independent Set called 3-Independent Set. Finally, simulation results suggest that sensing by point sampling is mostly applicable when poses are densely distributed in the plane.