| The Complexity of Sensing by Point Sampling | |||||||||||||||
Abstract | |||||||||||||||
| this paper we consider the problem of finding the minimum number of sensing points required to distinguish between a finite set of polygonal shapes. For instance, we might imagine embedding a series of point light detectors in a feeder tray. Then we would be interested in the question "What is the minimum number of light detectors that can fully distinguish between all the possible shapes?" Or we might imagine a set of mechanical probes that touches the feeder at a finite number of predetermined points. Then we would ask "What are the minimum number of probing points and where should the probes be located in order to distinguish all the possible shapes?" We address these questions in this paper. Intuitively, each sensing point can be regarded as a binary bit that has two values `contained' and `not contained '. So the robot senses a shape by reading out the binary representation of the shape, that is, by checking which points are contained in the shape and which are not. The formalized sensing problem: Given n polygons with a total of m edges in the plane, locate the fewest points such that each polygon contains a distinct subset of points in its interior. We show that this problem is equivalent to an NP-complete set-theoretic problem introduced as Discriminating Set. By a reduction to Hitting Set (and hence to Set Covering), an O(n | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||