On the order induced by a set of rays: application to the probing of nonconvex polygons

The authors present a strategy for discovering the exact shape of a simple (but not necessarily convex) polygon by means of a minimal number of simple probes. When each probe outcome consists of a contact point, a ray measuring that point and the normal to the object at the point, it is shown that 3n-3 probes are necessary and sufficient to discover the exact shape of a polygon with n noncollinear edges. Each probe can be determined in O(log n) time, yielding on O(n log n)-time O(n)-space algorithm