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
Altitude Terrain Guarding and Guarding Uni-Monotone Polygons
University of Texas at Dallas, Richardson, TX, USA.
Max Planck Institute for Informatics, Saarbrücken, Germany; Saarbrücken Graduate School of Computer Science, Saarbrücken, Germany.
University of Texas at Dallas, Richardson, TX, USA.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Show others and affiliations
2019 (English)In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081XArticle in journal (Refereed) Epub ahead of print
Abstract [en]

We present an optimal, linear-time algorithm for the following version of terrain guarding: given a 1.5D terrain and a horizontal line, place the minimum number of guards on the line to see all of the terrain. We prove that the cardinality of the minimum guard set coincides with the cardinality of a maximum number of “witnesses”, i.e., terrain points, no two of which can be seen by a single guard. We show that our results also apply to the Art Gallery problem in “monotone mountains”, i.e., x-monotone polygons with a single edge as one of the boundary chains. This means that any monotone mountain is “perfect” (its guarding number is the same as its witness number); we thus establish the first non-trivial class of perfect polygons.

Place, publisher, year, edition, pages
Elsevier, 2019.
Keywords [en]
Terrain Guarding Problem, Art Gallery Problem, Altitude Terrain Guarding Problem, Perfect Polygons, Monotone Polygons, Uni-monotone Polygons, Monotone Mountains
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-161302OAI: oai:DiVA.org:liu-161302DiVA, id: diva2:1366094
Available from: 2019-10-28 Created: 2019-10-28 Last updated: 2020-01-17Bibliographically approved

Open Access in DiVA

fulltext(2027 kB)4 downloads
File information
File name FULLTEXT02.pdfFile size 2027 kBChecksum SHA-512
9d6311b7962f66a0e652c58058ffcb79a91397665777c27d9f581dbc1639cb2cacb479c6f1cdff4cf361706e0c8d8a96381e2378f55c5ce56f80f1fc2f0b9aef
Type fulltextMimetype application/pdf

Other links

arXiv

Search in DiVA

By author/editor
Polishchuk, ValentinSchmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Computational geometry
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

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