A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. 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 2D case 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.
The data structure The dual of a convex hull of a set of points is the upper and lower envelopes of the dual set of lines. 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. Computing upper and lower envelopes are equivalent problems, so computing the upper envelope of a set of lines is equivalent to computing 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 merge step is performed using a vertical line sweep. Call the first set of points blue and the second set of points red. 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. When a point is encountered, the algorithm checks if the point is above or below the segment following the last encountered point of the opposite color. If it is above, that point is added to the merged upper envelope. If it is of a different color than the last added point, the red and blue envelopes have crossed, so the intersection point is also added to the merged upper envelope. The sequence of edges and vertices resulting from this algorithm is only dependent on the ordering of points, and the results of the line-point comparisons. Thus, the result can be certified with the following certificates:
x-certificates ( < x {\displaystyle <_{x}} ) are used to certify the order the vertices of the red and blue envelopes. They are the certificates for a kinetic sorted list on the set of vertices. Since each point involves 2 lines, and the certificate involves 2 points, each certificate involves 4 lines. y-certificates ( < y {\displaystyle <_{y}} ) are used to certify that a vertex is above or below an edge. The certificates appear for all comparisons that would occur during the algorithm. As long as all of these certificates hold, the merge steps will be executed identically, so the resulting upper envelope will be the same. A kinetic data structure for upper envelopes can be created by using these certificates to certify the static upper envelope algorithm. 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. Thus, it is necessary to introduce a s-certificates ( < s {\displaystyle <_{s}} ) which certifies that the slope of a line is greater than or less than the slope of another line.
Having the following certificates for all points ab is sufficient to certify the sequence of edges and vertices resulting from a merge, with only O(1) certificates per line:
x [ a b ] {\displaystyle x[ab]} : a b < x a b . n e x t {\displaystyle ab<_{x}ab.next} . a b . n e x t {\displaystyle ab.next} denotes vertex closest to a b {\displaystyle ab} on its right. This certificate is stored for all points a b {\displaystyle ab} which have a different color than the point, a b . n e x t {\displaystyle ab.next} , which follows them.
y l i [ a b ] {\displaystyle yli[ab]} : a b < y c e ( a b ) {\displaystyle ab<_{y}ce(ab)} or a b > y c e ( a b ) {\displaystyle ab>_{y}ce(ab)} . This certificate is stored for all points a b {\displaystyle ab} such that b {\displaystyle b} intersects c e ( a b ) {\displaystyle ce(ab)} . c e ( a b ) {\displaystyle ce(ab)} denotes the contender edge of a b {\displaystyle ab} , the edge from the other envelope that is above or below a b {\displaystyle ab} .
… excerpt ends here. Continue reading the full article.
