Kinetic Data Structures:Kinetic Data Structures

Kinetic Data Structures

Suppose we are interested in tracking high-level attributes of a geometric system of objects in motion such as, for example, the convex hull of a set on n points moving in R . Note that as the points move continuously, their convex hull will be a continuously evolving convex polygon. At certain discrete moments, however, the combinatorial structure of the convex hull will change (that is, the circular sequence of a subset of the points that appear on the hull will change). In between such moments, tracking the hull is straightforward: its geometry is determined by the positions of the sequence of points forming the hull. How can we know when the combinatorial structure of the hull changes? The idea is that we can focus on certain elementary geometric relations among the n points, a set of cached assertions, which altogether certify the correctness of the current combinatorial structure of the hull. If we have short-term information about the motion of the points, then we can predict failures of these assertions in the near future. Furthermore, we can hope to choose these certifying relations in such a way so that when one of them fails because of point motion, both the hull and its set of certifying relations can be updated locally and incrementally, so that the whole process can continue.

• Kinetic data structure: A kinetic data structure (KDS) for a geometric at- tribute is a collection of simple geometric relations that certifies the combinatorial structure of the attribute, as well as a set of rules for repairing the attribute and its certifying relations when one relation fails.

• Certificate: A certificate is one of the elementary geometric relations used in a KDS.

• Motion plan: An explicit description of the motion of an object in the near future.

• Event: An event is the failure of a KDS certificate during motion. If motion plans are available for all objects in a certificate, then the future time of failure for this certificate can be predicted. Events are classified as external when the combinatorial structure of the attribute changes, and internal, when the structure of the attribute remains the same, but its certification needs to change.

• Event queue: In a KDS, all certificates are placed in an event queue, according to their earliest failure time.

The inner loop of a KDS consists of repeated certificate failures and certification repairs, as depicted in Figure 23.1.

We remark that in the KDS framework, objects are allowed to change their motions at will, with appropriate notification to the data structure. When this happens all certificates involving the object whose motion has changed must re-evaluate their failure times.

Convex Hull Example

Suppose we have four points a, b, c, and d in R , and wish to track their convex hull.

For the convex hull problem, the most important geometric relation is the ccw predicate:

ccw(a, b, c) asserts that the triangle abc is oriented counterclockwise. Figure 23.2 shows a configuration of four points and four ccw relations that hold among them. It turns out that these four relations are sufficient to prove that the convex hull of the four points is the triangle abc. Indeed the points can move and form different configurations, but as long as the four certificates shown remain valid, the convex hull must be abc.

Now suppose that points a, b, and c are stationary and only point d is moving with a known plan, as shown in Figure 23.3. At some time t1 the certificate ccw(d, b, c) will fail, and at a later time t2 ccw(d, a, b) will also fail. Note that the certificate ccw(d, c, a) will never fail in the configuration shown even though d is moving. So the certificates ccw(d, b, c) and ccw(d, a, b) schedule events that go into the event queue. At time t1, ccw(d, b, c) ceases to be true and its negation, ccw(c, b, d), becomes true. In this simple case the three old certificates, plus the new certificate ccw(c, b, d) allow us to conclude that convex hull has now changed to abdc.

If the certificate set is chosen wisely, the KDS repair can be a local, incremental process— a small number of certificates may leave the cache, a small number may be added, and the new attribute certification will be closely related to the old one. A good KDS exploits the continuity or coherence of motion and change in the world to maintain certifications that themselves change only incrementally and locally as assertions in the cache fail.

Performance Measures for KDS

Because a KDS is not intended to facilitate a terminating computation but rather an on- going process, we need to use somewhat different measures to assess its complexity. In classical data structures there is usually a tradeoff between operations that interrogate a set of data and operations that update the data. We commonly seek a compromise by building indices that make queries fast, but such that updates to the set of indexed data are not that costly as well. Similarly in the KDS setting, we must at the same time have access to information that facilitates or trivializes the computation of the attribute of interest, yet we want information that is relatively stable and not so costly to maintain. Thus, in the same way that classical data structures need to balance the efficiency of access to the data with the ease of its update, kinetic data structures must tread a delicate path between “knowing too little” and “knowing too much” about the world. A good KDS will select a certificate set that is at once economical and stable, but also allows a quick repair of itself and the attribute computation when one of its certificates fails.

• responsiveness: A KDS is responsive if the cost, when a certificate fails, of repairing the certificate set and updating the attribute computation is small. By “small” we mean polylogarithmic in the problem size—in general we consider small quantities that are polylogarithmic or O(nE ) in the problem size.

• efficiency: A KDS is efficient if the number of certificate failures (total number of events) it needs to process is comparable to the number of required changes in the combinatorial attribute description (external events), over some class of allowed motions. Technically, we require that the ratio of total events to external events is small. The class of allowed motions is usually specified as the class of pseudo-algebraic motions, in which each KDS certificate can flip between true and false at most a bounded number of times.

• compactness: A KDS is compact if the size of the certificate set it needs is close to linear in the degrees of freedom of the moving system.

• locality: A KDS is local if no object participates in too many certificates; this condition makes it easier to re-estimate certificate failure times when an object changes its motion law. (The existence of local KDSs is an intriguing theoretical question for several geometric attribute functions.)

The Convex Hull, Revisited

We now briefly describe a KDS for maintaining the convex hull of n points moving around in the plane [16].

The key goal in designing a KDS is to produce a repairable certification of the geometric object we want to track. In the convex hull case it turns out that it is a bit more intuitive to look at the dual problem, that of maintaining the upper (and lower) envelope of a set of moving lines in the plane, instead of the convex hull of the primal points. Such dualities represent a powerful toolkit in computational geometry; readers are referred to any standard computational geometry textbook for details, for example [21]. For simplicity we focus only on the upper envelope of the moving lines from now on; the lower envelope case is entirely symmetric. Using a standard divide-and-conquer approach, we partition our lines into two groups of size roughly n/2 each, and assume that recursive invocations of the algorithm maintain the upper envelopes of these groups. For convenience call the groups red and blue.

In order to produce the upper envelope of all the lines, we have to merge the upper envelopes of the red and blue groups and also certify this merge, so we can detect when it ceases to be valid as the lines move; see Figure 23.4.

FIGURE 23.4: Merging the red and blue upper envelopes. In this example, the red envelope (solid line) is above the blue (dotted line), except at the extreme left and right areas. Vertical double-ended arrows represent y-certificates and horizontal double-ended arrows represent x-certificates, as described below.

Conceptually, we can approach this problem by sweeping the envelopes with a vertical line from left to right. We advance to the next red (blue) vertex and determine if it is above or below the corresponding blue (red) edge, and so on. In this process we determine when red is above blue or vice versa, as well as when the two envelopes cross. By stitching together all the upper pieces, whether red or blue, we get a representation of the upper envelope of all the lines.

The certificates used in certifying the above merge are of three flavors:

• x-certificates (<x) are used to certify to x-ordering among the red and blue vertices; these involve four original lines.

• y-certificates (<y ) are used to certify that a vertex is above or below an edge of the opposite color; these involve three original lines and are exactly the duals of the ccw certificates discussed earlier.

• s-certificates (<s) are slope comparisons between pairs of original lines; though these did not arise in our sweep description above, they are needed to make the KDS local [16].

Figure 23.5 shows examples of how these types of certificates can be used to specify x-ordering constraints and to establish intersection or non-intersection of the envelopes.

A total of O(n) such certificates suffices to verify the correctness of the upper envelope merge.

Whenever the motion of the lines causes one of these certificates to fail, a local, constant time process suffices to update the envelope and repair the certification. Figure 23.6 shows an example where an y-certificate fails, allowing the blue envelope to poke up above the red.

It is straightforward to prove that this kinetic upper envelope algorithm is responsive, local, and compact, using the logarithmic depth of the hierarchical structure of the certification. In order to bound the number of events processed, however, we must assume that the line motions are polynomial or at least pseudo-algebraic. A proof of efficiency can be developed by extruding the moving lines into space-time surfaces. Using certain well-known theorems about the complexity of upper envelopes of surfaces [43] and the overlays of such

envelopes [3] it can be shown that in the worst case the number of events processed by this algorithm is near quadratic (O(n2+E )). Since the convex hull of even linearly moving points can change Ω(n2) times [8], the efficiency result follows.

No comparable structure is known for the convex hull of points in dimensions d ≥ 3.