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

Math @ Duke





.......................

.......................


Publications [#235564] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharir, M, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry, vol. 1 no. 2 (1991), pp. 65-78, ISSN 0925-7721
    (last updated on 2017/12/12)

    Abstract:
    Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ1,...,σn) of n insert and delete operations on a set S of points in R2, initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog3n) and uses O(n) space. © 1991.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

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