Search: onr:"swepub:oai:DiVA.org:mau-57000" >
On Vertex Guarding ...
On Vertex Guarding Staircase Polygons
-
- Gibson-Lopez, Matt (author)
- The University of Texas at San Antonio, San Antonio, TX, United States
-
- Krohn, Erik (author)
- University of Wisconsin - Oshkosh, Oshkosh, WI, United States
-
- Nilsson, Bengt J. (author)
- Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
show more...
-
- Rayford, Matthew (author)
- University of Wisconsin - Oshkosh, Oshkosh, WI, United States
-
- Soderman, Sean (author)
- The University of Texas at San Antonio, San Antonio, TX, United States
-
- Żyliński, Paweł (author)
- University of Gdańsk, Gdańsk, Poland
-
show less...
-
(creator_code:org_t)
- 2022-10-29
- 2022
- English.
-
In: LATIN 2022: Theoretical Informatics. LATIN 2022. - Cham : Springer. ; , s. 746-760
- Related links:
-
https://rdcu.be/c2CK...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- In this paper, we consider the variant of the art gallery problem where the input polygon is a staircase polygon. Previous works on this problem gave a 2-approximation for point guarding a staircase polygon (where guards can be placed anywhere in the interior of the polygon and we wish to guard the entire polygon). It is still unknown whether this point guarding variant is NP-hard. In this paper we consider the vertex guarding problem, where guards are only allowed to be placed at the vertices of the polygon, and we wish to guard only the vertices of the polygon. We show that this problem is NP-hard, and we give a polynomial-time 2-approximation algorithm.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
To the university's database