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

Figure 3.5.
region of the Voronoi Order that is not a line.

On the exterior of a square with corners, each corner induces a level set

have the same Voronoi Order. Therefore, any two points of the same
Voronoi Order are connected by a path of the same Voronoi Order.
In Figure 3.1, the level sets of the Voronoi Order level sets are lines.
However, as shown in Figure 3.5, if the contour is not smooth, the
Voronoi Order may induce level sets that are connected regions, but
not lines.

T HEOREM 3.3 (V ORONOI O RDER F OR S MOOTH C ONTOURS ) Level
sets of the Voronoi Order for a smooth contour are line segments of finite
or infinite length.

Proof. At a given point, a smooth contour has a unique tangent and
hence up to orientation a unique normal v ( s ).

→

Given two points, x and

→

→

y, that have the same Voronoi Center z, and a contour C, since XZ and

→

YZ are Voronoi Projections, they must both follow the same normal v ( s )
and therefore are collinear.
For a smooth contour, the level sets of a contour are straight line seg-
ments and the Voronoi Order can uniquely describe any point of the
exterior (or interior) of the contour as a tuple of its Voronoi Order and
Voronoi Distance.
In summary, these theorems establish the Voronoi Ordering Space as a
warped version of 2-D image space. Given a contour C

∈

C , the level sets
of Voronoi Order partitions the image space into a series of connected
regions.

If we order these connected regions by their Voronoi Order

value, we can consider a subset of contours in

2 whose path moves from
region to region while monotonically increasing Voronoi Order value. In

ℜ