Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235429] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Varadarajan, KR, Efficient algorithms for approximating polygonal chains, Discrete and Computanional Geometry, vol. 23 no. 2 (2000), pp. 273-291
    (last updated on 2018/10/20)

    We consider the problem of approximating a polygonal chain C by another polygonal chain C′ whose vertices are constrained to be a subset of the set of vertices of C. The goal is to minimize the number of vertices needed in the approximation C′. Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ε ≥ 0, compute an approximation of C, among all approximations whose error is at most ε, that has the smallest number of vertices. We present an O(n4/3+δ)-time algorithm to solve this problem, for any δ > 0; the constant of proportionality in the running time depends on δ. (2) Given a polygonal chain C and an integer k, compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n4/3+δ), to solve this problem.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320