Removing Local Extrema from Imprecise Terrains

Details Removing Local Extrema from Imprecise Terrains Removing Local Extrema from Imprecise Terrains

2010-02-12

arxiv.org/abs/1002.2580v2

Computer Science

Computational Geometry

21 pages, revised version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Removing Local Extrema from Imprecise Terrains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Removing Local Extrema from Imprecise Terrains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Removing Local Extrema from Imprecise Terrains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-420516