A kinetic diameter data structure is a kinetic data structure which maintains the diameter of a set of moving points.
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 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.
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 pairs, and thus appear many times in the kinetic tournament.
The existence of a local kinetic data structure for diameter is open.
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.