8.1. General Terminology

8.1. General Terminology

In this section, we will introduce some terminology related to KDSs [Basch et al. 97, Guibas 98]. For the moment, this terminology might remain a bit abstract, but we will explain each of these terms again with a concrete example.

Attribute.   Denotes the output of the KDS. Examples: convex hull of a set of points, closest pair among a set of points. The attribute usually is part of the KDS. Sometimes, the KDS itself is the attribute (e. g., BSP).

Combinatorial structure.   The KDS without any coordinates (and probably any other float-like values). Examples: a graph, a tree, pointers. The combinatorial structure is usually part of the KDS.

Certificate.   A predicate over a number of objects from the input and the data structure. Examples: pn < 0 (point below/on/above plane), image from book (point c is left/on/right of line through points a , b ). The KDS maintains a number of certificates.

Proof.   A set of certificates with the following property: the combinatorial structure together with the current concrete values (coordinates) remains valid for the given set of inputs, as long as all certificates in the proof are true. Obviously, we will try to determine the minimal size of a proof for a KDS.

Failure time.   As the objects involved in a certificate move through their published flight path , that certificate eventually becomes false. The earliest time this happens is called the failure time or death time of the certificate. Since all flight paths are published, this can be computed, basically, by finding the smallest root of an algebraic function (which could become very complex).

Obviously, the KDS remains valid until the earliest failure time among all certificates in its proof.

Event.   This is another term for the failure of a certificate. There can be two reasons why a certificate fails, which are called external and internal events.

An external event occurs whenever the attribute (i.e., the output) of the KDS changes. At this time, one or more of the certificates must fail.

An event is called internal if a certificate has failed but the attribute of the KDS does not change.

Speaking of events only makes sense if the attribute of the KDS is unique. (For instance, the convex hull is unique, but a BSP is not.)

Efficient.   When designing a KDS one should strive to minimize the number of internal events. A KDS is called efficient if the ratio image from book in the worst case.

Response time.   This is the time (worst case or average case) needed to update the KDS whenever a certificate fails. If the response time is in O (log x n ), then the KDS is called responsive .

Compact.   A KDS is called compact, if the number of certificates in its proof is linear (or almost linear) in the size of the input.

Local.   A KDS is called local, if each object of the input participates only in a small (i.e., polylog) number of certificates. This is important because it ensures that the KDS can be updated efficiently if an object changes its flight path.

As a simple example of a KDS, we will present a kinetic BSP in the following example. It will be introduced in three steps:

  1. static segment tree;

  2. kinetic segment tree;

  3. kinetic BSP tree.

This is adapted from [de Berg et al. 01].



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net