Finding Minimum Witness Sets in Orthogonal Polygons

EasyChair Preprint 3170

Abstract

A \emph{witness set} $W$ in a polygon $P$ is a subset of $P$ such that any set $G \subset P$ that guards $W$ is guaranteed to guard $P$. We study the problem of finding a minimum witness set for an orthogonal polygon under three models of orthogonal visibility: rectangular, staircase and $k$-periscope visibility.

Under the traditional line-segment visibility, it is known that not all simple polygons admit a finite witness set and, when a polygon admits a finite minimal witness set, the witnesses must lie on the boundary of the polygon~\cite{chwa2006guarding}.

In this paper, we prove that every orthogonal polygon with $n$ vertices admits a finite witness set which has $O(n^2)$ witnesses under rectangular, staircase and $k$-periscope visibility. We also show that there exist orthogonal polygons which require $\Omega(n^2)$ witnesses under staircase visibility. Furthermore, we show that there exist orthogonal polygons for which the boundary is not a witness set for any of the three considered visibility models. Finally, we describe an $O(n^4)$ time algorithm to find a minimum witness set for a given orthogonal polygon under the rectangular %$k$-periscope and staircase visibility models.

Keyphrases: Art Gallery Problem, Orthogonal polygons, Periscope Visibility, Staircase Visibility, Witness Problem, rectangular visibility

@booklet{EasyChair:3170,
  author    = {Israel Aldana-Galván and Carlos Alegría-Galicia and José Luis Álvarez-Rebollar and Nestaly Marin-Nevárez and Erick Solís-Villarreal and Jorge Urrutia and Carlos Velarde},
  title     = {Finding Minimum Witness Sets in Orthogonal Polygons},
  howpublished = {EasyChair Preprint 3170},
  year      = {EasyChair, 2020}}