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
Optimum guard covers and m-watchmen routes for restricted polygons
Luleå University of Technology.
Department of Computer Science, Lund University.
Computer Science Program, University of Texas at Dallas.
1993 (English)In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 3, no 1, p. 85-105Article in journal (Refereed) Published
Abstract [en]

A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a path (route) which provide a natural connection between the Art Gallery problem, the m-watchmen problem and the watchman route problem. We prove that finding the minimum number of vision points, i.e., static guards, along a shortest watchman route is NP-hard. We provide a linear time algorithm to compute the best set of static guards in a histogram polygon. The m-watchmen problem, minimize total length of routes for m watchmen, is NP-hard for simple polygons. We give a \Theta(n 3 + n 2 m 2 )-time algorithm to compute the best set of m watchmen in a histogram. 1 Introduction The problem of placing guards in an art gallery so that every point in the gallery is visible to at least one guard has been considered by several researchers. If the gallery is represented by a polygon, ...

Place, publisher, year, edition, pages
1993. Vol. 3, no 1, p. 85-105
National Category
Mathematical Analysis
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:ltu:diva-3680DOI: 10.1142/S0218195993000063ISI: 000208795300005Local ID: 17ededc0-cbcc-11df-a707-000ea68e967bOAI: oai:DiVA.org:ltu-3680DiVA, id: diva2:976539
Note

Godkänd; 1993; 20100929 (andbra)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2021-12-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text
By organisation
Luleå University of Technology
In the same journal
International journal of computational geometry and applications
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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