Determining the shape of a convex n-sided polygon by using 2n + k tactile probes

We show that 2n + k tactile probes are sufficient to determine the shape of a convex polygon of n sides selected from a known finite set of polygons. This result improves on the 3n probe algorithm of Cole and Yap (1983) in the finite case. We show k = 3 under the assumptions of Cole and Yap, k = 2 under slightly stronger assumptions, and k = −1 under the assumptions of Schwartz and Sharir (1984).