  In this paper we consider imprecise terrains, that is, triangulated terrains
with a vertical error interval in the vertices. In particular, we study the
problem of removing as many local extrema (minima and maxima) as possible from
the terrain. 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. Interestingly,
however, removing both the minima and maxima simultaneously is NP-hard, and is
even hard to approximate within a factor of O(log log n) unless P=NP. Moreover,
we show that even a simplified version of the problem where vertices can have
only two different heights is already NP-hard, a result we obtain by proving
hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that
has lately received considerable attention from the graph-algorithms community.
