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
Finding the shortest watchman route in a simple polygon
Luleå University of Technology.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Department of Computer Science, Lund University.
1999 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 22, no 3, p. 377-402Article in journal (Refereed) Published
Abstract [en]

We present the first polynomial time algorithm that finds the shortest route in a simple polygon such that all points of the polygon are visible from the route. This route is called the shortest watchman route, and we do not assume any restrictions on the route or on the simple polygon. Our algorithm runs in worst case O(n6) time, but it is adaptive, making it run faster on polygons with a simple structure

Place, publisher, year, edition, pages
1999. Vol. 22, no 3, p. 377-402
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-4099DOI: 10.1007/PL00009467ISI: 000082298200005Scopus ID: 2-s2.0-0033465172Local ID: 1f7fa180-3fa7-11de-bc0c-000ea68e967bOAI: oai:DiVA.org:ltu-4099DiVA, id: diva2:976962
Note
Godkänd; 1999; 20090513 (andbra)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2023-05-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Jonsson, Håkan

Search in DiVA

By author/editor
Jonsson, Håkan
By organisation
Luleå University of TechnologyComputer Science
In the same journal
Discrete & Computational Geometry
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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