On the Complexity of Nonconvex Covering

DOI10.1137/0215031zbMath0603.68103OpenAlexW2046559210MaRDI QIDQ3740282

Wolfgang Maass

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215031

zbMATH Keywords

polynomial time algorithmNP-completenessroboticscomputational geometrydegree of nonconvexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Related Items

Location, pricing and the problem of Apollonius ⋮ The complexity of domination problems in circle graphs