Kinetic diameter (data)

A kinetic diameter data structure is a kinetic data structure which maintains the diameter of a set of moving points. The diameter of a set of moving points is the maximum distance between any pair of points in the set. In the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the diameter of a moving point set that is responsive, compact and efficient.

2D Case

The pair of points with maximum pairwise distance must be one of the pairs of antipodal points of the convex hull of all of the points. Note that two points are antipodal points if they have parallel supporting lines. In the static case, the diameter of a point set can be found by computing the convex hull of the point set, finding all pairs of antipodal points, and then finding the maximum distance between these pairs. This algorithm can be kinetized as follows:

Consider the dual of the point set. The points dualize to lines and the convex hull of the points dualizes to the upper and lower envelope of the set of lines. The vertices of the upper convex hull dualize to segments on the upper envelope. The vertices of the lower convex hull dualize to segments on the lower envelope. The range of slopes of the supporting lines of a point on the hull dualize to the x-interval of segment that point dualizes to. When viewed in this dualized fashion the antipodal pairs, are pairs of segments, one from the upper envelope, one from the lower, with overlapping x ranges. Now, the upper and lower envelopes can be viewed as two different x-ordered lists of non overlapping intervals. If these two lists are merged, the antipodal pairs are the overlaps in the merged list.

The overlaps in the merged list of x-intervals can be maintained by storing the endpoints of the intervals in a kinetic sorted list. When points swap, the list of antipodal pairs are updated. The upper and lower envelopes can be maintained using the standard data structure for kinetic convex hull. The maximum distance between pairs of antipodal can be maintained with a kinetic tournament. Thus, using kinetic convex hull to maintain the upper and lower envelopes, a kinetic sorted list on these intervals to maintain the antipodal pairs, and a kinetic tournament to maintain the pair of maximum distance apart, the diameter of a moving point set can be maintained.

This data structure is responsive, compact and efficient. The data structure uses $O(n)$ space because the kinetic convex hull, sorted list, and tournament data structures all use $O(n)$ space. In all of the data structures, events, inserts, and deletes can be handled in $O(\log ^{2}n)$ time, so the data structure are responsive, requiring $O(\log ^{2}n)$ per event. The data structure is efficient because the total number of events is $O(n^{2+\epsilon })$ for all $\epsilon >0$ and the diameter of a point set can change $\Omega (n^{2})$ times, even if the points are moving linearly. This data structure is not local because one point may be in many antipodal pairs, and thus appear many times in the kinetic tournament.

The existence of a local kinetic data structure for diameter is open.

Higher Dimensions

Efficiently maintaining the kinetic diameter of a point set in dimensions higher than 2 is an open problem. Efficient kinetic convex hull in dimensions higher than 2 is also an open problem.

Related Problems

• Kinetic width
• Kinetic minimum box

References

P. K. Agarwal, L. J. Guibas, J. Hershberger, and E. Verach. Maintaining the extent of a moving set of points.