Removing Local Extrema from Imprecise Terrains

Chris Gray, Frank Kammer, Maarten Löffler, Rodrigo I. Silveira

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    Abstract

    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.
    Original languageEnglish
    Title of host publicationProc. 26th European Workshop on Computational Geometry
    Pages181-184
    Number of pages4
    Publication statusPublished - 2010

    Keywords

    • CG, GIS, TIN, IMP

    Fingerprint

    Dive into the research topics of 'Removing Local Extrema from Imprecise Terrains'. Together they form a unique fingerprint.

    Cite this