Kinetic convex hull
A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points.
[1] It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete changes such as insertions or deletions of points rather than continuous motion.
The best known data structure for the 2-dimensional kinetic convex hull problem is by Basch, Guibas, and Hershberger.
This data structure is responsive, efficient, compact and local.
Therefore, maintaining the upper and lower envelopes of a set of moving lines is equivalent to maintaining the convex hull of a set of moving points.
The upper envelope of a set of static lines can be computed using a divide and conquer algorithm which partitions the lines into two sets of equal size, calls itself recursively on the two sets to find their upper envelopes, and then merges the two resulting upper envelopes.
The standard line sweep algorithm for merging upper envelopes sweeps though all of vertices of the red and blue upper envelopes, from left to right.
The most recently encountered red and blue points are maintained as the line sweeps.
However, this scheme is not local, because one line many be involved in many y-certificates if it remains on top or bottom as many points from the other envelope are encountered.
Unlike the previous scheme all lines are only involved in a constant number of certificates.
The kinetic data structure for convex hull is constructed by using these certificates to certify the recursive merge of the upper envelopes.
[1] This data structure is responsive, local, compact, and efficient.
This is due to the logarithmic depth of the merges used to certify the upper envelope.
[1] Finding an efficient kinetic data structure for maintaining the convex hull of moving points in dimensions higher than 2 is an open problem.
[1] Kinetic convex hull can be used to solve the following related problems:[6]
