Finding minimum witness sets in orthogonal polygons
| Autor: | C. Alegría, Israel Aldana-Galván, Jose Luis Álvarez-Rebollar, Jorge Urrutia, Erick Solís-Villarreal, Carlos Velarde, N. Marín |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Control and Optimization
0102 computer and information sciences 02 engineering and technology Computer Science::Computational Geometry 01 natural sciences Upper and lower bounds Witness Computer Science Applications Combinatorics Computational Mathematics Computational Theory and Mathematics 010201 computation theory & mathematics Polygon 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Guard (computer science) Geometry and Topology Witness set ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | Computational Geometry. 90:101656 |
| ISSN: | 0925-7721 |
| DOI: | 10.1016/j.comgeo.2020.101656 |
| Popis: | A witness set W in a polygon P is a subset of P such that any set G ⊂ 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. 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 ( n 2 ) 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 ( n 4 ) time under rectangular and staircase visibility, and in O ( n 6 ) time under k-periscope visibility. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect