Incremental and decremental maintenance of planar width

We present an algorithm for maintaining the width of a planar point set dyn amically, as points are inserted or deleted. Our algorithm takes time O(kn( epsilon)) par 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 epsilon > 0 is a ny arbitrarily small constant. For incremental or decremental update sequen ces, the amortized time per update is O(n(epsilon)). (C) 2000 Academic Pres s.