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
How to Keep an Eye on Small Things
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-1342-8618
Institute of Informatics, University of Gdańsk, 80-308 Gdańsk, Poland.
2020 (English)In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 30, no 02, p. 97-120Article in journal (Refereed) Published
Abstract [en]

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having 𝑛n edges. We also prove that in polygons with holes, there is a constant 𝑐>0c>0 such that no polynomial-time algorithm can solve the problem within an approximation factor of 𝑐log𝑛clogn, unless P=NP. For the second problem, we present a (𝑘+ℎ)(k+h)-FPT algorithm for computing a shortest tour that sees 𝑘k specified points in a polygon with ℎh holes. We also present a 𝑘k-FPT approximation algorithm for this problem having approximation factor 2‾√2. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of 𝑐log𝑛clogn, for some constant 𝑐>0c>0, unless P=NP.

Place, publisher, year, edition, pages
World Scientific, 2020. Vol. 30, no 02, p. 97-120
Keywords [en]
Visibility, guarding, approximation algorithm, FPT-algorithm
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:mau:diva-56822DOI: 10.1142/s0218195920500053Scopus ID: 2-s2.0-85101295110OAI: oai:DiVA.org:mau-56822DiVA, id: diva2:1720771
Available from: 2022-12-20 Created: 2022-12-20 Last updated: 2024-02-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Nilsson, Bengt J.

Search in DiVA

By author/editor
Nilsson, Bengt J.
By organisation
Department of Computer Science and Media Technology (DVMT)
In the same journal
International journal of computational geometry and applications
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 79 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