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.
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
ab
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)
O(n)
O(log2n)
O(log2n)
O(n2+\epsilon)
\epsilon>0
\Omega(n2)
The existence of a local kinetic data structure for width is open.
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.
P. K. Agarwal, L. J. Guibas, J. Hershberger, and E. Verach. Maintaining the extent of a moving set of points.