Kinetic and dynamic data structures for convex hulls and upper envelopes

摘要

Let S be a set of it moving points in the plane. We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of S. The structure uses O(n) space, and processes all expected number of O(n(2)beta(s+2)(n) log n) critical events, each in O(log(2)n) expected time, including O(n) insertions, deletions, and changes in the flight plans of the points. Here s is the maximum number of times where any specific triple of points can become collinear, beta(s) (q) = lambda(s)(q)/q, and lambda(s)(q) is the maximum length of Davenport-Schinzel sequences of order s on it symbols. Compared with the previous solution of Basch, Guibas and Hershberger [J. Basch, L.J. Guibas, J. Hershberger, Data structures for mobile data, J. Algorithms 31 (1999) 1-28], our structure uses simpler certificates, uses roughly the same resources, and is also dynamic. (c) 2006 Elsevier B.V. All rights reserved.