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 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 () 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 () 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 () 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: Convex hulls of linearly moving points can change \Omega(n^2) times. Thus this data structure is efficient. ==Higher dimensions==