Off-line dynamic maintenance of the width of a planar point set

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • January 1, 1991

Published In

Volume / Issue

  • 1 / 2

Start / End Page

  • 65 - 78

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/0925-7721(91)90001-U

Citation Source

  • Scopus