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

✍ Scribed by Pankaj K. Agarwal; Micha Sharir

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 967 KB
• Volume: 1
• Category: Article
• ISSN: 0925-7721
• DOI: 10.1016/0925-7721(91)90001-u

✦ Synopsis

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 X = (a,, , a,,) 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(n log3 n) and uses O(n) space.

' A problem involving optimization over pairs of points in a set S is called decomposable if S x S can be broken into subsets, the optimizing pair in each subset can be computed separately, and the grand optimum can be obtained by combining all these partial results.