An efficient algorithm for terrain simplification
Pankaj K. Agarwal, Pavan K. Desikan · 1997
Given a set S of n points in ! 3 , sampled from an unknown bivariate function f(x; y) (i.e., for each point p 2 S, z p = f(x p ; y p )), a piecewise-linear function g(x; y) is called an "-approximation of f(x; y) if for every p 2 S, jf(x; y) \\Gamma g(x; y)j ". The problem of computing an "-approximation with the minimum number of vertices is NP-Hard. We present a randomized algorithm that computes an "-approximation of size O(c 2 log 2 c) in O(n 2+ffi + c 3 log 2 c log n c ) expected time, where c is the size of the "-approximation with the minimum number of vertices and ffi is any arbitrarily small positive number. Under some reasonable assumptions, the size of the output is close to O(c log c) and the expected running time is O(n 2+ffi ). We have implemented a variant of this algorithm and include some empirical results. 1 Introduction Modeling and construction of surfaces representing objects is an important area in many scientific disciplines like Geographic In...