Removing local extrema from imprecise terrains

详细信息	查看全文 | 推荐本文 |

• 作者：Chris Gray^a ; ^{gray@ibr.cs.tu-bs.de} ; Frank Kammer^b ; ^{kammer@informatik.uni-augsburg.de} ; Maarten Lö ; ffler^c ; ^{mloffler@uci.edu} ; Rodrigo I. Silveira^d ; ^{rodrigo.silveira@upc.edu}
• 关键词：Data imprecision ; Terrain analysis ; Local minima ; P2-MaxCon ; P2-Con
• 刊名：Computational Geometry
• 出版年：2012
• 期刊代码：18_09257721
• 类别：cp
• 出版时间：August, 2012
• 卷：45
• 期：7
• 页码：334-349
• 文件大小：479 K

摘要

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; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices 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.