liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • 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.
Show others and affiliations
2024 (English)In: Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024), 2024Conference paper, Published paper (Other academic)
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.

Place, publisher, year, edition, pages
2024.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-214969OAI: oai:DiVA.org:liu-214969DiVA, id: diva2:1970741
Conference
36th Canadian Conference on Computational Geometry (CCCG 2024), Brock University, St. Catharines, Canada, July 17 - 19, 2024
Available from: 2025-06-17 Created: 2025-06-17 Last updated: 2025-06-17

Open Access in DiVA

No full text in DiVA

Other links

Förlagets fulltext/Publisher's full text

Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 19 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf