Document Open Access Logo

A Sweep-Plane Algorithm for Calculating the Isolation of Mountains

Authors Daniel Funke, Nicolai Hüning, Peter Sanders

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.51.pdf
  • Filesize: 4.82 MB
  • 17 pages

Document Identifiers

Author Details

Daniel Funke
  • Karlsruhe Institute of Technology, Germany
Nicolai Hüning
  • Karlsruhe Institute of Technology, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Germany

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 882500).

Cite As Get BibTex

Daniel Funke, Nicolai Hüning, and Peter Sanders. A Sweep-Plane Algorithm for Calculating the Isolation of Mountains. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.51

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • computational geometry
  • Geo-information systems
  • sweepline algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Pankaj K. Agarwal, Lars Arge, Thomas Mølhave, and Bardia Sadri. I/O-efficient efficient algorithms for computing contours on a terrain. In Proceedings of the twenty-fourth annual symposium on Computational geometry. ACM, June 2008. URL: https://doi.org/10.1145/1377676.1377698.
  2. Christopher J. Amante, Matthew Love, Kelly Carignan, Michael G. Sutherland, Michael MacFerrin, and Elliot Lim. Continuously Updated Digital Elevation Models (CUDEMs) to Support Coastal Inundation Modeling. Remote Sensing, 15(6), 2023. URL: https://doi.org/10.3390/rs15061702.
  3. Efthymios G. Anagnostou, Leonidas J. Guibas, and Vassilios G. Polimenis. Topological sweeping in three dimensions. In Tetsuo Asano, Toshihide Ibaraki, Hiroshi Imai, and Takao Nishizeki, editors, Algorithms, pages 310-317, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg. Google Scholar
  4. Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891-923, 1998. Google Scholar
  5. M. Axtmann, S. Witt, D. Ferizovic, and P. Sanders. In-Place Parallel Super Scalar Samplesort (IPSSSSo). In 25th Annual European Symposium on Algorithms, volume 87, pages 9:1-9:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.9.
  6. M.K. Barker, E. Mazarico, G.A. Neumann, M.T. Zuber, J. Haruyama, and D.E. Smith. A new lunar digital elevation model from the Lunar Orbiter Laser Altimeter and SELENE Terrain Camera. Icarus, 273:346-355, 2016. URL: https://doi.org/10.1016/j.icarus.2015.07.039.
  7. J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, pages 643-647, 1979. Google Scholar
  8. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, September 1975. URL: https://doi.org/10.1145/361002.361007.
  9. Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning, pages 97-104, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1143844.1143857.
  10. COMNAP: Council of Managers of National Antarctic Programs. Antarctic Station Catalogue, 2017. Online; accessed 22-Apr-2023. URL: https://www.comnap.aq/s/COMNAP_Antarctic_Station_Catalogue.pdf.
  11. Mark de Berg and Constantinos Tsirogiannis. Exact and approximate computations of watersheds on triangulated terrains. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, November 2011. URL: https://doi.org/10.1145/2093973.2093985.
  12. Jonathan de Ferranti. Digital elevation data, 2011. Online; accessed 05-Juli-2022. URL: http://viewfinderpanoramas.org/dem3.html.
  13. R. Dementiev, L. Kettner, and P. Sanders. STXXL: Standard Template Library for XXL data sets. Software Practice & Experience, 38(6):589-637, 2008. Google Scholar
  14. Alaska Satellite Facility. Radarset antarctic mapping, 2008. URL: https://asf.alaska.edu/data-sets/derived-data-sets/radarsat-antarctic-mapping-project-ramp/.
  15. R. A. Finkel and J. L. Bentley. Quad trees a data structure for retrieval on composite keys. Acta Informatica, 4(1):1-9, 1974. URL: https://doi.org/10.1007/bf00288933.
  16. Peter Fisher and Jo Wood. What is a mountain? or the englishman who went up a boolean geographical concept but realised it was fuzzy. Geography, pages 247-256, 1998. Google Scholar
  17. Peter Fisher, Jo Wood, and Tao Cheng. Where is helvellyn? fuzziness of multi-scale landscape morphometry. Transactions of the Institute of British Geographers, 29(1):106-128, 2004. Google Scholar
  18. S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2(1):153-174, 1987. Google Scholar
  19. Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), 3(3):209-226, 1977. Google Scholar
  20. Daniel Funke, Nicolai Hüning, and Peter Sanders. A Sweep-plane Algorithm for Calculating the Isolation of Mountains. Technical report, Karlsruhe Intitute of Technology, May 2023. URL: https://doi.org/10.48550/arXiv.2305.08470.
  21. Bundesamt für Landestopografie swisstopo. swissALTI 3D Das hoch aufgelöste Terrainmodell der Schweiz, March 2022. Google Scholar
  22. L. H. Graff and E. L. Usery. Automated classification of generic terrain features in digital elevation models. Photogrammetric Engineering and Remote Sensing, 59(9):1409-1417, 1993. Google Scholar
  23. Peter Grimm. Die Gebirgsgruppen der Alpen: Ansichten, Systematiken und Methoden zur Einteilung der Alpen. Deutscher Alpenverein, 2004. Google Scholar
  24. K. Gwinner, F. Scholten, F. Preusker, S. Elgner, T. Roatsch, M. Spiegel, R. Schmidt, J. Oberst, R. Jaumann, and C. Heipke. Topography of Mars from global mapping by HRSC high-resolution digital terrain models and orthoimages: Characteristics and performance. Earth and Planetary Science Letters, 294(3-4):506-519, 2010. Google Scholar
  25. Heather Hanson. Shuttle radar topography mission (srtm). Technical report, NASA, 2019. Online; access 21-september-2022. URL: https://eospso.gsfc.nasa.gov/missions/shuttle-radar-topography-mission.
  26. Adam Helman. The Finest Peaks-Prominence and Other Mountain Measures. Trafford Publishing, 2005. Google Scholar
  27. Johann H Jungclaus, Stephan J Lorenz, Hauke Schmidt, Victor Brovkin, Nils Brüggemann, Fatemeh Chegini, Traute Crüger, Philipp De-Vrese, Veronika Gayler, Marco A Giorgetta, et al. The ICON earth system model version 1.0. Journal of Advances in Modeling Earth Systems, 14(4):e2021MS002813, 2022. Google Scholar
  28. Andrew Kirmse and Jonathan de Ferranti. Calculating the prominence and isolation of every mountain in the world. Progress in Physical Geography, 41(6):788-802, 2017. Google Scholar
  29. National Center for Geospatial Intelligence Standards. World geodetic system 1984: Its definition and relationships with local geodetic systems. Technical Report NGA.STND.0036_1.0.0_WGS84, Department of Defense, 2014. Google Scholar
  30. PeakVisor. Peakvisor. Online; accessed 22-Apr-2023. URL: https://peakvisor.com/panorama.html.
  31. Mathias Rav, Aaron Lowe, and Pankaj K. Agarwal. Flood risk analysis on terrains. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, November 2017. URL: https://doi.org/10.1145/3139958.3139985.
  32. E Rodriguez, CS Morris, JE Belz, EC Chapin, JM Martin, W Daffer, and S Hensley. An assessment of the SRTM topographic products. Technical Report JPL D-31639, Jet Propulsion Laboratory, 2005. Google Scholar
  33. Erich Schubert, Arthur Zimek, and Hans-Peter Kriegel. Geodetic distance queries on r-trees for indexing geographic data. In Advances in Spatial and Temporal Databases, pages 146-164. Springer, Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40235-7_9.
  34. Greg Slayden. Peakbagger. Online; accessed 22-Apr-2023. URL: https://peakbagger.com.
  35. Michiel Smid. Closest-point problems in computational geometry. In Handbook of computational geometry, pages 877-935. Elsevier, 2000. Google Scholar
  36. Tetsushi Tachikawa, Masami Hato, Manabu Kaku, and Akira Iwasaki. Characteristics of ASTER GDEM version 2. In 2011 IEEE International Geoscience and Remote Sensing Symposium, pages 3657-3660, 2011. URL: https://doi.org/10.1109/IGARSS.2011.6050017.
  37. Rocio Nahime Torres, Piero Fraternali, Federico Milani, and Darian Frajberg. A deep learning model for identifying mountain summits in digital elevation model data. In IEEE First International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), pages 212-217. IEEE, 2018. Google Scholar
  38. Rocio Nahime Torres, Federico Milani, and Piero Fraternali. Algorithms for mountain peaks discovery: a comparison. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, pages 667-674, 2019. Google Scholar
  39. Dimitra I. Vassilaki and Athanassios A. Stamos. TanDEM-X DEM: Comparative performance review employing LIDAR data and DSMs. ISPRS Journal of Photogrammetry and Remote Sensing, 160:33-50, 2020. URL: https://doi.org/10.1016/j.isprsjprs.2019.11.015.
  40. Wang Yitao, Yang Lei, and Song Xin. Route mining from satellite-AIS data using density-based clustering algorithm. Journal of Physics: Conference Series, 1616(1):012017, August 2020. URL: https://doi.org/10.1088/1742-6596/1616/1/012017.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact