Digital Signal Processing Reference
In-Depth Information
We now relate pivots through their Voronoi Areas.
T
HEOREM
3.5 (P
IVOT
C
ONTAINMENT
)
Given a contour C
C
,
A
∈
Φ(
C,b
)
where a and b are different Voronoi Pivots, if
→
→
→
Φ(
C,a
),
and B
→
→
the
Voronoi Pivot of B, b, is contained in A, then B is contained within
A.
→
Proof.
If
b
is contained within A,
then the minimal distance projec-
→
tions of
b
are also contained within A, since they cannot go outside of A
without intersecting the minimal distance projections of
→
boundaries of B are within A and the portion of the contour perimeter
that B borders is less than
a.
Since all the
1
, B is contained by A.
2
T
HEOREM
3.6 (V
ORONOI
P
IVOT
C
ONTAINMENT
)
Given a contour C
→
→
C
,
A
Φ(
C, a
),
→
and a Voronoi Pivot b, if a Voronoi Pivot b is contained
→
in the interior of Voronoi Area A and A
Φ(
C,b
),
every Voronoi Area
|
→
in
Φ(
C,b
)
is contained in A.
→
Proof.
b
Since every Voronoi Area in Φ(
C, b
) has the same Voronoi Pivot
→
→
→
and
b
is contained in A, A contains all Voronoi Areas in Φ(
C, b
).
Finally, we need one definition in order to relate the values of χ
V
with
the Voronoi Areas.
D
EFINITION
3.5 ( V
ORONOI
-C
ONTAINMENT
V
ORONOI
P
IVOTS
)
A
FOR
→
→
pivot a is said to Voronoi-contain a pivot b iff any Voronoi Area in
Φ(
a
)
→
→
contains all Voronoi Areas in
Φ(
b
).
With
these
definitions
and
theorems,
we
define
the
multiresolution
property of this containment relation over interior of a contour C E C.
T
HEOREM
3.7 (T
REE
S
TRUCTURE OF
V
ORONOI
P
IVOTS
)
Given a con-
C
,
the Voronoi-Containment relation over the Voronoi Pivots
on the interior of C induces a forest, i.e., a set of trees. Each node
in each tree is a pivot in the interior of C and the parent-descendant
relation in each tree follows the
tour C
Voronoi-containment
of pivots.
Proof.
Let us consider all Voronoi Pivots on the interior of C as set I.
These Voronoi Pivots can be divided trivially into two sets: points that
are Voronoi-contained by another Voronoi Pivot and those that are not,
S and
S,
respectively. We partition pivots in I by which point in S they
are Voronoi-contained. Let us consider one partition T, a set of these
pivots. Voronoi Containment induces a tree on the set T, where a node is
a member of T and the paths in the tree describe the parent-descendant
relation that follows the Voronoi-containment relation because:
-
Search WWH ::
Custom Search