Probing polygons minimally is hard
type: Item
instance of: scholarly article
title: Probing polygons minimally is hard
zbMATH Open document ID: 0782.68112
DOI: 10.1016/0925-7721(93)90022-X
author: Patrice Belleville
author: Thomas C. Shermer
published in: Computational Geometry
publication date: 1993-06-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 220606
zbMATH Keywords: probing
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: Geometric algorithms and combinatorial optimization
cites work: Q4198056
cites work: Probing convex polygons with half-planes
full work available at URL: 0925-7721(93)90022-x
OpenAlex ID: W1995282992
description: scientific article; zbMATH DE number 220606