A kinetic tournament is organized in a binary tree-like structure, where the leaves containthe elements, and each internal node contains the larger of the elements in its child nodes. Thus, the root of the tree contains the maximum element at a given time. The validity of the structure is enforced by creating a certificate at each node, which asserts that the element in the node is the larger of the two children. When this certificate fails, the element at the node is changed, and a new certificate representing the new invariant is created. If the element this node was a winner at its parent node, then the element and certificates at the parent must be recursively updated too.
Analysis
This is a O space, responsive, local, compact and efficient data-structure.
Responsiveness:A certificate failure will cause the creation of a new certificate to replace the old one, which must be put into the event queue. It may also trigger changes to the O certificates at its parent nodes. Each certificate change requires a delete and insert operation in the priority queue of events. Each of these takes O time, so the responsiveness, the total time required to process an certificate failure, is. While this is considered responsive in general, it is less responsive than other kinetic priority queues such as kinetic heaps which respond to certificate failures with O certificate changes.
Locality: Each element is involved in O certificates. Again, while this is considered local, a kinetic heap is much more local.
Compactness: This is a very compact structure, containing O certificates - exactly one for every edge in the tree.
Efficiency: Kinetic heaps are very efficient, with the number of internal events being only a factor of O more than the number of external events. Specifically, for a collection of space-time trajectories where each pair intersects at most times, the kinetic tournament processes events in time, where is a Davenport-Schinzel sequence. Additionally, insertions and deletions cause O certificate changes each. Each certificate change takes O time, which is determined by the time required to execute the event queue update.
