Math @ Duke

Publications [#235580] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Suri, S, Surface approximation and geometric partitions,
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
(1994),
pp. 2433
(last updated on 2017/12/10)
Abstract: Motivated by applications in scientific computation, visualization, and computer graphics, we study the computational complexity of the following problem: Given a set S of n points sampled from a bivariate function f(x,y) and an input parameter ε<0, compute a piecewise linear function Σ(x,y) of minimum complexity (that is, a xymonotone polyhedral surface, with a minimum number of vertices, edges, or faces) such that Σ(xp,yp)zp≤ε, for any (xp,yp,zp) ∈ S. We prove that the decision version of this problem is NPHard. The main result of our paper is a polynomialtime approximation algorithm that computes a piecewise linear surface of size O(Ko log Ko), where Ko is the complexity of an optimal surface satisfying the constraints of the problem. The technique developed in our paper is more general and applies to several other problems that deal with partitioning of points (or other objects) subject to certain geometric constraints. For instance, we get the same approximation bound for the following problem, which arises in machine learning: given n `red' and m `blue' points in the plane, find a minimum number of pairwise disjoint triangles such that each blue point is covered by some triangle and no red point lies in any of the triangles.


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

