Terrain prickliness: theoretical grounds for low complexity viewsheds

Abstract

An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position.

In this work we study a new topographic attribute, the prickliness, that measures the number of local maxima in a terrain from all possible perspectives. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.

Corresponding Publications

Terrain prickliness: theoretical grounds for low complexity viewsheds

Ankush Acharyya, Ramesh Jallu, Maarten Löffler, Gert Meijer, Maria Saumell, Rodrigo I. Silveira, Frank Staals, Hans Raj Tiwary

Proc. 11th International Conference on Geographic Information Science, 2021

To Appear.
@incollection{prickliness2021,
  author = {Acharyya, Ankush and Jallu, Ramesh and  L{\"o}ffler, Maarten and
                 Meijer, Gert and Saumell, Maria and I. Silveira, Rodrigo and
                 Staals, Frank and Raj Tiwary, Hans},
  title = {Terrain prickliness: theoretical grounds for low complexity viewsheds},
  booktitle = {Proc. 11th International Conference on Geographic Information Science},
  year = {2021},
  location = {(online)},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  numpages = {14},
  category = {terrains},
  note = {To Appear.},
}

Terrain prickliness: theoretical grounds for low complexity viewsheds

Ankush Acharyya, Ramesh Jallu, Maarten Löffler, Gert Meijer, Maria Saumell, Rodrigo I. Silveira, Frank Staals, Hans Raj Tiwary

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

@article{prickliness_eurocg,
  author = {Acharyya, Ankush and Jallu, Ramesh and  L{\"o}ffler, Maarten and
                 Meijer, Gert and Saumell, Maria and I. Silveira, Rodrigo and
                 Staals, Frank and Raj Tiwary, Hans},
  title = {Terrain prickliness: theoretical grounds for low complexity viewsheds},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {other},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_34.pdf},
  project = {prickliness2021},
}