VORONOI ORDERED SPACE - Video Object Extraction and Representation: Theory and Applications - page 61

Voronoi Ordered Space 61

1. Every node is connected to the root.
Every Voronoi Area is Voronoi-contained by one pivot in T.

2. There are no cycles in the graph.
Two different Voronoi pivots that contain each other contradict the-

orem 3.6.

3. There are no reconverging paths.
A

reconverging path implies that there exists two different Voronoi

Areas that do not contain each other, but contain a common pivot

and, consequently, have a common area, contradicting theorem 3.4.

Therefore, Voronoi Containment on the set of points in T induces a

tree. Applying this analysis to every partition, Voronoi Containment

induces a forest over the Voronoi Pivots of C.
In Chapter 6, we wish to have a single rooted tree to represent a shape
contour. For the case where forest contain multiple trees, we merely
create another node and join all roots of trees to this node to create a tree
with a single root. Although, in theory, theorem 3.7 implies that there
may be multiple trees, in practice, after thousands of tree extractions,
we have always found that the tree has only one root. We conjecture
that the forest in theorem 3.7 is always a single tree. Although a proof
of this conjecture would allow for a more elegant analysis, it is irrelevant
for our applications and beyond the scope of this topic.
The next step is to relate the containment structure of Voronoi Pivots
and the χ V values by defining a function that quantifies a measure of

Voronoi- Containment.

D EFINITION 3.6 (T HE S PAN V ORONOI A REA ) Given a Voronoi OF A

Area A, the spanning function α( C, A ) returns the length of the perimeter

of A that coincides with C.

This function on Voronoi Areas allows the containment relation be-

tween Voronoi Areas to be expressed as a value relation.

T HEOREM 3.8 (C ONTAINMENT I NDICATOR ) For a given contour C, two

Voronoi Areas, A and B,

A contains B →α( C, A ) ≤ α( C, B ).

(3.7)

Proof. If Voronoi Area A contains B, then the perimeter of B that

borders the contour C is also contained by the perimeter of A that

borders C.
Now we may proceed to our final result.