Information Technology Reference
In-Depth Information
(a)
(b)
(c)
(d)
Fig. 4.
Steps of the algorithm for the CST problem. (a) An input with
n
=10points and
k
=3.
(b) Computing minimum spanning trees. (c) Bounding the tree having the shortest length, and
removing red-blue crossings. (d) Merging with the green tree.
We b egin with the description of ouralgorithm in the setting when the input consists
of blue and red points. First, we compute a minimum spanning tree of the blue points
(ignoring the red ones), and a minimum spanning tree of the red points; see Fig.4(b).
If the trees do not intersect, then they form a solution for CST. Otherwise, we create a
red “shell” bounding the bluetree;seeFig.4(c). Now red-blue crossings appear inside
the constructed shell, and they can be eliminated by removing all portions of the red
tree inside the shell. Finally, the red curve, consisting of the original spanning tree
and the constructed shell, can be transformed to a tree by disconnecting its cycles; see
Fig.4(d).
The general algorithm works in the following steps. First, create a minimumtree
MST(
C
i
) spanning the set of points
C
i
for 1
≤ i ≤ k
,ignoring points of the other
colors. Sort the colors with respect to the length of the corresponding spanning trees.
Withoutlossofgenerality, we may assume that the resulting order is
C
1
,...,C
k
and
|
. Then the resulting curve for
C
1
is the tree MST(
C
1
).
Acurve for each successive color
C
i
is constructed by adding a “shell” bounding the
MST(
C
1
)
|≤···≤|
MST(
C
k
)
|
curve corresponding to
C
i−
1
.Thelength of the shell is exactly 2
j<i
|
,
since it bounds all the spanning trees corresponding to already processed colors; see
Fig.4.Thelength of a curve for
C
i
is then
MST(
C
j
)
|
+2
j<i
|
.
In order to analyze the algorithm, we denote the amount of ink in the optimal so-
lution by OPT, and the total length of the constructed solution by ALG. An optimal
solution induces a curve connecting all points of the same cluster, that is, the solution
is a Steiner tree for the set of points (but not necessarily the minimum one). Hence,
OPT
|
MST(
C
i
)
|
MST(
C
j
)
|
≥
i
|
|≥
i
|
SMT(
C
i
)
MST(
C
i
)
|
/ˁ
. On the other hand,
=
k
j
=1
|
i−
1
k
≤
|
MST(
C
i
)
|
MST(
C
j
)
|
(2
k
−
2
i
+1)
|
MST(
C
i
)
|
,
and
ALG
+2
i
=1
i
=1
i
=1
(2
k −
2
i
+1)
|
MST(
C
i
)
|
i
=1
|
ALG
OPT
≤
=
MST(
C
i
)
|
/ˁ
=
ˁ
k/
2
+
k/
2
i
=1
(2
k
−
2
i
+1)
|
MST(
C
i
)
|
(2
i
−
1)
|
MST(
C
k−i
+1
)
|
i
=1
≤
kˁ.
i
=1
|
MST(
C
i
)
|
Hence, ouralgorithm is a (
kˁ
)-approximation for the CST problem for any
k
≥
1.
