Kinetic convex hull

Last updated November 11, 2022

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 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 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.^[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:

x-certificates ( $<_{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}$ ) 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}$ ) 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]

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. Kinetic convex hull, detection of intersections.png — 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.

$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.
$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$ .
$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)$ .
$yt[ab]$ : $ce(ab)<_{y}ab$ . This certificate is stored for all points $ab$ for which $a<_{s}ce(ab)<_{s}b$ and $ce(ab)<_{y}ab$ .
$srt[ab]$ : $a<_{s}ce(ab)$ . This certificate is stored for all points $ab$ for which $a<_{s}ce(ab)<_{s}b$ and $ce(ab)<_{y}ab$ .
$srt[ab]$ : $ce(ab)<_{s}b$ . This certificate is stored for all points $ab$ for which $a<_{s}ce(ab)<_{s}b$ and $ce(ab)<_{y}ab$ .
$sl[ab]$ : $b<_{s}ce(ab)$ . This certificate is stored for all points $ab$ for which $b<_{s}ce(ab)$ and $ab<_{y}ce(ab)$ .
$sr[ab]$ : $ce(ab)<_{s}a$ . This certificate is stored for all points $ab$ for which $ce(ab)<_{s}a$ and $ab<_{y}ce(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]

Responsive: When a certificate fails, it takes O(1) to fix the merge it certifies. If the resulting envelope changes, the change must be propagated up to all merges that depend on the result of the changed merge. There are O(log n) such mergers, so the update can be performed in O(log n) time total.
Local: Each line is involved in a most O(log n) certificates. This is because each line is involved in a constant number of certificates in each merge, and each line is in O(log n) merges total.
Compactness: The maximum number of certificates used in this data structure is O(n log n). This is because each merge involves a number of certificates linear to the number of lines merged. Certifying an upper envelope of n lines requires certificates for the merge upper envelope of the two subsets of n/2 lines, and certificates for the merge of the envelopes. Thus the number of certificates, C(n), required to certify the upper envelope of n lines satisfies the recurrence C(n)=2C(n/2)+O(n), with C(1)=O(1). By the master theorem for divide-and-conquer recurrences, C(n)=O(n log n).
Efficiency: The maximum number of events processed by this algorithm on algebraic or pseudo-algebraic trajectories is near quadratic, $O(n^{2+\epsilon })$ for all $\epsilon >0$ .^[3]^[4] Convex hulls of linearly moving points can change $\Omega (n^{2})$ times.^[5] Thus this data structure is efficient.

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 Research Articles

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

<span class="mw-page-title-main">Graham scan</span> Algorithm for computing convex hulls in a set of points

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

<span class="mw-page-title-main">Point-set triangulation</span>

A triangulation of a set of points $in the Euclidean space is a simplicial complex that covers the convex hull of, and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.$

In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986, combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.

<span class="mw-page-title-main">Orthogonal convex hull</span> Minimal superset that intersects each axis-parallel line in an interval

In geometry, a set $K \subset R d$ is defined to be orthogonally convex if, for every line $L$ that is parallel to one of standard basis vectors, the intersection of $K$ with $L$ is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.

<span class="mw-page-title-main">Chan's algorithm</span>

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set $of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output. In the planar case, the algorithm combines an algorithm with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick-Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.$

The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.

The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with $time complexity, where is the number of input points and is the number of points in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick-Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick-Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.$

Quickhull is a method of computing the convex hull of a finite set of points in n-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case complexity for 2-dimensional and 3-dimensional space is considered to be $, where is the number of input points and is the number of processed points. However, unlike quicksort, there is no obvious way to convert quickhull into a randomized algorithm. Nevertheless, there exist works from Smoothed Analysis which tell us that the 2-dimensional Quick hull algorithm has expected runtime . Indeed, and related works show that the number of points on the convex hull of any randomly perturbed pointset with Gaussian noise is from which it follows that Quick hull can only takes time on any set of perturbed points.$

A kinetic data structure is a data structure used to track an attribute of a geometric system that is moving continuously. For example, a kinetic convex hull data structure maintains the convex hull of a group of $moving points. The development of kinetic data structures was motivated by computational geometry problems involving physical objects in continuous motion, such as collision or visibility detection in robotics, animation or computer graphics.$

A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property – if $B$ is a child node of $A$ , then the priority of the element in $A$ must be higher than the priority of the element in $B$ . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue to maintain certificate failure times.

A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set P of n points that are moving continuously with time in a metric space. While many efficient algorithms were known in the static case, they proved hard to kinetize, so new static algorithms were developed to solve this problem.

A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order. It is used as a kinetic predecessor data structure, and as a component in more complex kinetic data structures such as kinetic closest pair.

A kinetic diameter data structure is a kinetic data structure which maintains the diameter of a set of moving points. The diameter of a set of moving points is the maximum distance between any pair of points in the set. In the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the diameter of a moving point set that is responsive, compact and efficient.

A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.

A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum priority element when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.

A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points. In 2D, the width of a point set is the minimum distance between two parallel lines that contain the point set in the strip between them. For the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the width of a point set that is responsive, compact and efficient.

Kinetic minimum box is a kinetic data structure to maintain the minimum bounding box of a set of points whose positions change continuously with time. For points moving in a plane, the kinetic convex hull data structure can be used as a basis for a responsive, compact and efficient kinetic minimum box data structure.

In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.

References

1 2 3 4 5 6 Basch, Julien; Guibas, Leonidas J.; Hershberger, John (April 1999). "Data structures for mobile data" (PDF). Journal of Algorithms. 31 (1): 1–28. CiteSeerX 10.1.1.134.6921 . doi:10.1006/jagm.1998.0988. S2CID 8013433.
↑ 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.
↑ Agarwal, Pankaj K.; Schwarzkopf, Otfried; Sharir, Micha (January 1996). "The overlay of lower envelopes and its applications". Discrete & Computational Geometry . 15 (1): 1–13. CiteSeerX 10.1.1.54.5488 . doi:10.1007/BF02716576. S2CID 1261935.
↑ Sharir, Micha (1994). "Almost tight upper bounds for lower envelopes in higher dimensions". Discrete & Computational Geometry . 12 (1): 327–345. doi: 10.1007/BF02574384 .
↑ Agarwal, Pankaj K.; Guibas, Leonidas J.; Hershberger, John; Veach, Eric (January 2001). "Maintaining the extent of a moving point set". Discrete & Computational Geometry . 26 (3): 353–374. CiteSeerX 10.1.1.47.8510 . doi:10.1007/s00454-001-0019-x.
↑ 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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[BGH99-1] 1 2 3 4 5 6 Basch, Julien; Guibas, Leonidas J.; Hershberger, John (April 1999). "Data structures for mobile data" (PDF). Journal of Algorithms. 31 (1): 1–28. CiteSeerX 10.1.1.134.6921 . doi:10.1006/jagm.1998.0988. S2CID 8013433.

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

[ASS96-3] Agarwal, Pankaj K.; Schwarzkopf, Otfried; Sharir, Micha (January 1996). "The overlay of lower envelopes and its applications". Discrete & Computational Geometry . 15 (1): 1–13. CiteSeerX 10.1.1.54.5488 . doi:10.1007/BF02716576. S2CID 1261935.

[Sha94-4] Sharir, Micha (1994). "Almost tight upper bounds for lower envelopes in higher dimensions". Discrete & Computational Geometry . 12 (1): 327–345. doi: 10.1007/BF02574384 .

[AGHV01-5] Agarwal, Pankaj K.; Guibas, Leonidas J.; Hershberger, John; Veach, Eric (January 2001). "Maintaining the extent of a moving point set". Discrete & Computational Geometry . 26 (3): 353–374. CiteSeerX 10.1.1.47.8510 . doi:10.1007/s00454-001-0019-x.

[AGHV97-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.

[1]

[2]

[3]

[4]

[5]

[6]