Kinetic width

A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points. In 2D, the width of a point set is the minimum distance between two parallel lines that contain the point set in the strip between them. For the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the width of a point set that is responsive, compact and efficient.

2D case

Consider the parallel lines which contain the point set in the strip between them and are of minimal distance apart. One of the lines must contain an edge $ab$ of the convex hull, and the other line must go through a point c of the convex hull such that (a,c) and (b,c) are antipodal pairs. ab and c are referred to as an antipodal edge-vertex pair. 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. If a pair $ab$ and c is an antipodal edge-vertex pair, then the x-interval for a and b must both intersect the x-interval for c. This means that the common endpoint of the x intervals for a and b must lie within the x-interval for c.

The endpoints of both of the sets of x-intervals can be maintained in a kinetic sorted list. When points swap, the list of antipodal edge-point pairs are updated appropriately. The upper and lower envelopes can be maintained using the standard data structure for kinetic convex hull. The minimum distance between edge-point pairs 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 edge-vertex pairs, and a kinetic tournament to maintain the pair of minimum 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 width 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 edge-vertex pairs, and thus appear many times in the kinetic tournament.

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

Higher Dimensions

Efficiently maintaining the kinetic width 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.^[1]

Related Problems

• Kinetic diameter
• Kinetic minimum box

References

1. Guibas, Leonidas J. (2001), "Kinetic Data Structures" (PDF), in Mehta, Dinesh P.; Sahni, Sartaj, Handbook of Data Structures and Applications, Chapman and Hall/CRC, pp. 23–1–23–18, ISBN 978-1584884354

Further reading

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