๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Incremental and Decremental Maintenance of Planar Width

โœ Scribed by David Eppstein

Book ID
102573649
Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
176 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present an algorithm for maintaining the width of a planar point set ลฝ โ‘€ . dynamically, as points are inserted or deleted. Our algorithm takes time O kn per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and โ‘€ ) 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is ลฝ โ‘€ . O n .

๐Ÿ“œ SIMILAR VOLUMES

Off-line dynamic maintenance of the widt
Off-line dynamic maintenance of the width of a planar point set
โœ Pankaj K. Agarwal; Micha Sharir ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 967 KB

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