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.

Journal Article (peer-reviewed)

Workshop or Poster (weakly reviewed)

Archived Publication (not reviewed)

back to list