License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.51
URN: urn:nbn:de:0030-drops-187040
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18704/
Go to the corresponding LIPIcs Volume Portal


Funke, Daniel ; H√ľning, Nicolai ; Sanders, Peter

A Sweep-Plane Algorithm for Calculating the Isolation of Mountains

pdf-format:
LIPIcs-ESA-2023-51.pdf (5 MB)


Abstract

One established metric to classify the significance of a mountain peak is its isolation. It specifies the distance between a peak and the closest point of higher elevation. Peaks with high isolation dominate their surroundings and provide a nice view from the top. With the availability of worldwide Digital Elevation Models (DEMs), the isolation of all mountain peaks can be computed automatically. Previous algorithms run in worst case time that is quadratic in the input size. We present a novel sweep-plane algorithm that runs in time ?(nlog n+pT_NN) where n is the input size, p the number of considered peaks and T_NN the time for a 2D nearest-neighbor query in an appropriate geometric search tree. We refine this to a two-level approach that has high locality and good parallel scalability. Our implementation reduces the time for calculating the isolation of every peak on Earth from hours to minutes while improving precision.

BibTeX - Entry

@InProceedings{funke_et_al:LIPIcs.ESA.2023.51,
  author =	{Funke, Daniel and H\"{u}ning, Nicolai and Sanders, Peter},
  title =	{{A Sweep-Plane Algorithm for Calculating the Isolation of Mountains}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18704},
  URN =		{urn:nbn:de:0030-drops-187040},
  doi =		{10.4230/LIPIcs.ESA.2023.51},
  annote =	{Keywords: computational geometry, Geo-information systems, sweepline algorithms}
}

Keywords: computational geometry, Geo-information systems, sweepline algorithms
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023
Supplementary Material: Software: https://github.com/dfunke/mountains archived at: https://archive.softwareheritage.org/swh:1:dir:9081f9961a7408668c156e998a1facb21b93e7dc


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI