Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

Dietmar Schuchardt, Hans‐Dietrich Hecker

Source record

Source: Crossref

Published: Jan 1, 1995

DOI: 10.1002/malq.19950410212

Open original source ↗

Source abstract

Abstract D. T. Lee and A. K. Lin [2] proved that VERTEX‐GUARDING and POINT‐GUARDING are NP‐hard for simple polygons. We prove that those problems are NP‐hard for ortho‐polygons, too.

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.