• Tipo:
  • Journal Article
Finding minimum witness sets in orthogonal polygons

A witness set W in a polygon P is a subset of P such that any set GcP 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. It is known that not all simple polygons admit a finite witness set under the traditional line-segment visibility and, if a polygon admits a finite minimal witness set, then the witnesses must lie on the boundary of the polygon [5]. In this paper, we prove that every orthogonal polygon with n vertices admits a finite witness set with O(n2) witnesses under rectangular, staircase, and k-periscope visibility. This upper bound is tight under staircase visibility. We also show an orthogonal polygon whose boundary is not a witness set for any of the three considered visibility models. We finally describe how to find a minimum witness set for a given orthogonal polygon in O(n4) time under rectangular and staircase visibility, and in O(n6) time under k-periscope visibility.

Aldana-Galván, I., Alegría, C., Álvarez-Rebollar, J. L., Marin, N., Solís-Villarreal, E., Urrutia, J., & Velarde, C. (2020). Finding minimum witness sets in orthogonal polygons. Computational Geometry, 90, 101656.