ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE

Efficient online algorithms are presented for maintaining the (almost-exact) width and diameter of a dynamic planar point-set, S. Let n be the number of points currently in S, let W and D denote the width and diameter of S, respectively, and let alpha > 1 and beta >= 1 be positive, integer-valued parameters. The algorithm for the width problem uses O(alpha n) space, supports updates in O(alpha log(2) n) time, and reports in O(alpha log(2) n) time an approximation, (W) over cap, to the width such that (W) over cap /W <= root 1+tan(2) pi/2 alpha. The algorithm for the diameter problem uses O(beta n) space, supports updates in O(beta log n) time, and reports in O(beta) time an approximation, (D) over cap, to the diameter such that (D) over cap /D >= sin(beta/beta+1 pi/2). Thus, for instance, even for a as small as 11, (W) over cap /W <= 1.01, and for beta as small as 9, (D) over cap /D > .99. All bounds stated are worst-case. Both algorithms, but especially the one for the diameter problem, use well-understood data structures and should be simple to implement. The diameter result yields a fast implementation of the greedy heuristic for maximum-weight Euclidean matching and an efficient online algorithm to maintain approximate convex hulls in the plane.