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/
Funke, Daniel ;
Hüning, Nicolai ;
Sanders, Peter
A Sweep-Plane Algorithm for Calculating the Isolation of Mountains
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}
}
