Logo image
Back
Geometric and combinatorial methods for digital elevation models
Dissertation   Open access

Geometric and combinatorial methods for digital elevation models

Scott Myers Haag
Doctor of Philosophy (Ph.D.), Drexel University
Oct 2019
DOI:
https://doi.org/10.17918/6t2f-sj31
pdf
Haag_Scott_20199.47 MBDownloadView
PDF Open Access Open Access (License Unspecified)

Abstract

Mathematical statistics--Data processing Geometrical models--Computer simulation Digital elevation models Computer Engineering
Digital Elevation Models (DEMs) are the de facto 3D models used to represent geo-spatial structures in many natural systems and are used in process-based modeling. From a computational perspective, DEMs are discrete, 2D manifold-grids in 3D space from which flow properties can be computed. An important family of problems involves identifying iso-flow surfaces from DEMs at discrete locations. In practical terms, such iso-flow surfaces correspond to sub-regions of the 3D-manifold whose aggregate flow passesthrough a single grid cell. Algorithmic solutions to these types of problems have numerous applications in Geographic Information Systems and Environmental Science research, allowing the efficient mapping of watershed boundaries. Existing algorithms for identifying iso-surfaces run in quadratic complexity as a function of the number of cells on their boundary. Our investigation shows that linear time algorithms to identify iso-surfaces are possible due to the combinatorial geometric properties of DEMs. Finally, a general method to return univariate statistical values for an iso-flow surfaces is developed. These algorithms rely on a number of new data structures, the Modified Nested Sets, Log Reduced Nested Sets, and a Modified Interval Search Tree. In empirical tests we show significant ( 500 faster) for a number of these iso-surface problems.

Metrics

61 File views/ downloads
31 Record Views

Details

Logo image