Math @ Duke

Publications [#235589] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Desikan, PK, Efficient algorithm for terrain simplification,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1997),
pp. 139147
(last updated on 2017/12/14)
Abstract: Given a set S̄ of n points in R3, sampled from an unknown bivariate function f(x, y) (i.e., for each point p ∈ S̄, zp = f(xp, yp)), a piecewiselinear function g(x, y) is called an εapproximation of f(x, y) if for every p ∈ S̄, f(x,y)g(x,y)≤ε. The problem of computing an εapproximation with the minimum number of vertices is NPHard. We present a randomized algorithm that computes an εapproximation of size O(c2log2 c) in O(n2+δ+c3log2clog n/c) expected time, where c is the size of the εapproximation with the minimum number of vertices and δ is any arbitrarily small positive number. Under some reasonable assumptions, the size of the output is close to O(clog c) and the expected running time is O(n2+δ). We have implemented a variant of this algorithm and include some empirical results.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

