Image Processing Reference
In-Depth Information
examined whether some face of this hull is a Nearest SP of P. As there are
n 2 points in P, the construction of CH(P) takes O(n 2 logn) time [110].
It can be shown that it is su cient to construct the convex hull of a subset
of points of a DPS P to obtain the USF F. In that case, a USF of P can be
found in O(n 2 ) time if it exists, where (n + 1) 2 is the number of points in P.
We observe that the LSF may also be obtained in O(n 2 ) time similarly.
Recall that if D is a DSLS, then it can be represented by a four tuple
(n,p,q,s) and the following line is a pre-image of D (refer to Section 3.1.2).
L : y = p
q (x−s) +⌈ sp
q
We note that L is a Nearest Upper Support Line that must pass through at
least one point of D. Let the rightmost and leftmost point of L be called
limiting points of L.
Definition 3.15. The limiting point set Lim(P) of a DPS P is defined as:
Lim(P) = {p|p ∈ P and p is a limiting point of some column DSLS P j ,0 ≤
j ≤ n }.
The following theorem is central to the algorithm to compute a USF of a
DPS.
Theorem 3.15. If there is a USF F of an n-DPS P, then F must be a face
of the convex hull of the set Lim(P) [42].
Thus to search for the Upper Supporting Face F of a DPS P it is su cient
to construct the convex hull of the points belonging to the set Lim(P) only.
Next we present the Algorithm Find Upper Support Face to compute
the USF (see Algorithm 6).
In the next theorem we analyze the time complexity of the algorithm.
Theorem 3.16. The algorithm runs in O(n 2 ) time where (n + 1) 2
is the
number of points in the DPS P.
3.4.3 Characterization by Convex Hull Separability
Stojmenovic in [201] presented an accurate characterization by using Con-
vex Hull Separability.
Let S be a set of 3-D points and S z+1 = {(i,j,k + 1) : (i,j,k) ∈ S}. A
plane γ in the Euclidean space separates the sets S 1 , S 2 in 3-D digital space
iff S 1 and S 2 are in opposite open half-spaces defined by γ. The following
theorem from to [201] provides a characterization of a digital plane.
Theorem 3.17. A set S in 3-D digital space is a subset of a digital plane iff
there exists a plane that separates S from S z+1 .
Search WWH ::




Custom Search