Math @ Duke

Publications [#235564] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, Offline dynamic maintenance of the width of a planar point set,
Computational Geometry, vol. 1 no. 2
(1991),
pp. 6578, ISSN 09257721
(last updated on 2018/02/19)
Abstract: Agarwal, P.K. and M. Sharir, Offline dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 6578. In this paper we present an efficient algorithm for the offline 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 277080320

