Probing polygons minimally is hard (Q1803270)

A polygon \(P\) is unimodal if the distance function from a vertex of \(P\) to all other vertices in counterclockwise order around the boundary of \(P\) has exactly one local maximum. A finger probe \(\pi\) is a directed line aimed at a simple polygon; \(\pi\) distinguishes between two polygons \(P\) and \(P'\) if the contact point of \(\pi\) with \(P\) differs from the contact point of \(\pi\) with \(P'\). Let \(\Gamma\) be a set of convex unimodal polygons in fixed position and orientation. The authors prove that the problem of determining whether \(k\) finger probes are sufficient to distinguish among the polygons in \(\Gamma\) is NP-complete for two types of finger probes. This implies that the same results hold for most interesting classes of polygons on which finger proves can be used.