liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Dispersive Vertex Guarding for Simple and Non-Simple Polygons
Department of Computer Science, TU Braunschweig.
Department of Applied Mathematics and Statistics, Stony Brook University.
Department of Computer Science, TU Braunschweig.
Faculty of Electrical Engineering and Computer Science, Bochum University of Applied Sciences.
Vise andre og tillknytning
2024 (engelsk)Inngår i: Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024), 2024Konferansepaper, Publicerat paper (Annet vitenskapelig)
Abstract [en]

We study the Dispersive Art Gallery Problem with vertex guards: Given a polygon P, with pairwise geodesic Euclidean vertex distance of at least 1, and a rational number ℓ; decide whether there is a set of vertex guards such that P is guarded, and the minimum geodesic Euclidean distance between any two guards(the so-called dispersion distance) is at least ℓ.We show that it is NP-complete to decide whether a polygon with holes has a set of vertex guards with dispersion distance 2. On the other hand, we provide an algorithm that places vertex guards in simple polygons at dispersion distance at least 2. This result is tight, as there are simple polygons in which any vertex guard set has a dispersion distance of at most 2.

sted, utgiver, år, opplag, sider
2024.
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-214969OAI: oai:DiVA.org:liu-214969DiVA, id: diva2:1970741
Konferanse
36th Canadian Conference on Computational Geometry (CCCG 2024), Brock University, St. Catharines, Canada, July 17 - 19, 2024
Tilgjengelig fra: 2025-06-17 Laget: 2025-06-17 Sist oppdatert: 2025-06-17

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Förlagets fulltext/Publisher's full text

Søk i DiVA

Av forfatter/redaktør
Schmidt, Christiane
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 20 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf