liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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: 2019-11-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

arXiv

Authority records BETA

Polishchuk, ValentinSchmidt, Christiane

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

urn-nbn

Altmetric score

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

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