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]

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.[1]

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 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.[2]

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:

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) 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:[1]

A picture of the certificates in several difference cases
The certificates certify structure of the intersection of the red and blue envelopes by certifying intersections(top left) or the absence of intersections(top right and bottom). The arrows indicate which elements are being compared by the certificate.
  1. x[ab]: ab<_x ab.next. ab.next denotes vertex closest to ab on its right. This certificate is stored for all points ab which have a different color than the point, ab.next, which follows them.
  2. yli[ab]: ab<_y ce(ab) or ab>_y ce(ab). This certificate is stored for all points ab such that b intersects ce(ab). ce(ab) denotes the contender edge of ab, the edge from the other envelope that is above or below ab.
  3. yri[ab]: ab<_y ce(ab) or ab>_y ce(ab). This certificate is stored for all points ab such that a intersects ce(ab).
  4. yt[ab]: ce(ab)<_yab. This certificate is stored for all points ab for which a<_sce(ab)<_s b and ce(ab)<_yab.
  5. srt[ab]: a<_sce(ab). This certificate is stored for all points ab for which a<_sce(ab)<_s b and ce(ab)<_yab.
  6. srt[ab]: ce(ab)<_s b. This certificate is stored for all points ab for which a<_sce(ab)<_s b and ce(ab)<_yab.
  7. sl[ab]: b<_sce(ab). This certificate is stored for all points ab for which b<_sce(ab) and ab<_yce(ab).
  8. sr[ab]: ce(ab)<_sa. This certificate is stored for all points ab for which ce(ab)<_sa and ab<_yce(ab).

The first certificate, x[ab], certifies the x-ordering of the points in the red and blue envelopes. The second and third certificates, yli[ab] and yri[ab], certify intersections of the red and blue envelopes. The remaining 5 certificates, yt[ab], srt[ab], srt[ab], sl[ab], and sr[ab] place edges that are not in the upper envelopes in the sequence of slopes of the edges that are above it. If the slope is at the start or end of the sequence, sl or sr certify this. If it is in the middle of the sequence slt, and srt certify this, and yt certifies that the intersection point of the two lines that the edge's slope is in between, is above it. These one or three certificates suffice to prove that all of the edges are above this line. Unlike the previous scheme all lines are only involved in a constant number of certificates. Whenever of these certificates fail, the merged envelope and certificates can be updated in O(1) time.

The kinetic data structure for convex hull is constructed by using these certificates to certify the recursive merge of the upper envelopes. Whenever certificates fail, their merge is updated, and if the envelope resulting from the merge changes, the changes are propagated up through all merges that depend on the result of the merge.[1]

Performance

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]

Higher dimensions

Finding an efficient kinetic data structure for maintaining the convex hull of moving points in dimensions higher than 2 is an open problem.[1]

Related Problems

Kinetic convex hull can be used to solve the following related problems:[6]

References

  1. 1 2 3 4 5 6 Basch, Julien; Guibas, Leonidas J.; Hershberger, John (April 1999). "Data structures for mobile data" (PDF). J. Algorithms 31 (1): 128. doi:10.1006/jagm.1998.0988.
  2. Hershberger, John (21 December 1989). "Finding the upper envelope of n line segments in O(n log n) time". Information Processing Letters 33 (4): 169–174. doi:10.1016/0020-0190(89)90136-1.
  3. Agarwal, Pankaj K.; Schwarzkopf, Otfried; Sharir, Micha (January 1996). "The overlay of lower envelopes and its applications". Discrete and Computational Geometry 15 (1): 1–13. doi:10.1007/BF02716576.
  4. Sharir, Micha (1994). "Almost tight upper bounds for lower envelopes in higher dimensions. Discrete and Computational Geometry" 12 (1): 327–345. doi:10.1007/BF02574384.
  5. Agarwal, Pankaj K.; Guibas, Leonidas J.; Hershberger, John; Veach, Eric (January 2001). "Maintaining the extent of a moving point set". Discrete and Computational Geometry 26 (3): 353–374. doi:10.1007/s00454-001-0019-x.
  6. Agarwal, Pankaj K.; Guibas, Leonidas J.; Hershberger, John; Veach, Eric (August 1997). "Maintaining the extent of a moving point set". Lecture Notes in Computer Science Volume 1272. 5th Workshop on Algorithms and Data Structures (WADS '97). pp. 31–44. doi:10.1007/3-540-63307-3_46.
This article is issued from Wikipedia - version of the Monday, October 19, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.