liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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.
Visa övriga samt affilieringar
2024 (Engelska)Ingår i: Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024), 2024Konferensbidrag, Publicerat paper (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
2024.
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-214969OAI: oai:DiVA.org:liu-214969DiVA, id: diva2:1970741
Konferens
36th Canadian Conference on Computational Geometry (CCCG 2024), Brock University, St. Catharines, Canada, July 17 - 19, 2024
Tillgänglig från: 2025-06-17 Skapad: 2025-06-17 Senast uppdaterad: 2025-06-17

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext/Publisher's full text

Sök vidare i DiVA

Av författaren/redaktören
Schmidt, Christiane
Av organisationen
Kommunikations- och transportsystemTekniska fakulteten
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 20 träffar
RefereraExporteraLänk till posten
Permanent länk

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