Removing Local Extrema from Imprecise Terrains

In this paper, we study imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. We study the problem of removing as many local extrema (minima and maxima) from the terrain as possible. We show that removing only minima or only maxima can be done optimally in O(n log n) time, for a terrain with n vertices, while removing both at the same time is NP-hard. To show hardness, we exploit a connection to a graph problem that is a special case of 2-Disjoint Connected Subgraphs, a problem that has received quite some attention lately in the graph theory community.

keywords: Computational Geometry, Geographical Information Analysis, Data Imprecision, Terrains

Journal Article (peer-reviewed)

Chris Gray, Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
Removing Local Extrema from Imprecise Terrains
Computational Geometry: Theory and Applications
45, 334–349, 2012
http://dx.doi.org/10.1016/j.comgeo.2012.02.002

Workshop or Poster (weakly reviewed)

Chris Gray, Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
Removing Local Extrema from Imprecise Terrains
Proc. 26th European Workshop on Computational Geometry
181–184, 2010

Archived Publication (not reviewed)

Chris Gray, Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
Removing Local Extrema from Imprecise Terrains
1002.2580, 2010
http://arXiv.org/abs/1002.2580

back to list