Sökning: onr:"swepub:oai:DiVA.org:mau-57000" >
On Vertex Guarding ...
On Vertex Guarding Staircase Polygons
-
- Gibson-Lopez, Matt (författare)
- The University of Texas at San Antonio, San Antonio, TX, United States
-
- Krohn, Erik (författare)
- University of Wisconsin - Oshkosh, Oshkosh, WI, United States
-
- Nilsson, Bengt J. (författare)
- Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
visa fler...
-
- Rayford, Matthew (författare)
- University of Wisconsin - Oshkosh, Oshkosh, WI, United States
-
- Soderman, Sean (författare)
- The University of Texas at San Antonio, San Antonio, TX, United States
-
- Żyliński, Paweł (författare)
- University of Gdańsk, Gdańsk, Poland
-
visa färre...
-
(creator_code:org_t)
- 2022-10-29
- 2022
- Engelska.
-
Ingår i: LATIN 2022: Theoretical Informatics. LATIN 2022. - Cham : Springer. ; , s. 746-760
- Relaterad länk:
-
https://rdcu.be/c2CK...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)