Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Segment Watchman Routes
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT). Malmö University, Sustainable Digitalisation Research Centre (SDRC).ORCID iD: 0000-0002-2161-6571
The Open University of Israel, Israel.
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT). Malmö University, Sustainable Digitalisation Research Centre (SDRC).ORCID iD: 0000-0002-1342-8618
University of Kassel, Germany.
Show others and affiliations
2025 (English)In: 41st European Workshop on Computational Geometry (EuroCG 2025: Booklet of Abstracts, 2025, article id 33Conference paper, Published paper (Refereed)
Abstract [en]

We consider a variant of the 2-watchmen problem that ensures that every point in a polygon P is seen from more than one direction: we search for routes W1, W2, such that for each p ∈ P there exist w1 ∈ W1, w2 ∈ W2 that see p and such that p ∈ w1w2 ⊂ P. We show that finding the two routes that are optimal with respect to the min-max criterion is NP-hard in simple polygons and present a 2-approximation algorithm for this case; moreover, we provide a polynomial-time algorithm for computing the two optimal routes with respect to the min-sum criterion in convex polygons. Finally, we discuss a generalized version of the problem with more than two watchmen.

Place, publisher, year, edition, pages
2025. article id 33
National Category
Algorithms Geometry
Identifiers
URN: urn:nbn:se:mau:diva-79435OAI: oai:DiVA.org:mau-79435DiVA, id: diva2:1997737
Conference
41st European Workshop on Computational Geometry, (EuroCG) April 9-11, 2025, Liblice
Available from: 2025-09-14 Created: 2025-09-14 Last updated: 2026-03-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Fulltext

Authority records

Brötzner, AnnaNilsson, Bengt J.

Search in DiVA

By author/editor
Brötzner, AnnaNilsson, Bengt J.
By organisation
Department of Computer Science and Media Technology (DVMT)Sustainable Digitalisation Research Centre (SDRC)
AlgorithmsGeometry

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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