A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points.
Consider the parallel lines which contain the point set in the strip between them and are of minimal distance apart.
Now, the upper and lower envelopes can be viewed as two different x-ordered lists of non overlapping intervals.
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.
space because the kinetic convex hull, sorted list, and tournament data structures all use
In all of the data structures, events, inserts, and deletes can be handled in
The data structure is efficient because the total number of events is
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.
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.