Information Technology Reference
In-Depth Information
If four corners are occupied, the robot which occupies the corner farthest from
c
is moved in an arbitrary direction, generating a configuration where only three
corners are occupied.
It remains the case where the minimal wrapping even
even sub-grid which
includes all the occupied nodes of the original grid has dimension 2
×
2. The con-
figuration is ungatherable on this sub-grid without multiplicity detection. However,
in the case of exactly three nodes occupied, it is possible to exploit the larger di-
mensions of the original grid in order to avoid the multiplicity detection. The cases
of two or four nodes occupied clearly remain ungatherable. The strategy is then to
move the robot on the corner of the 2
×
2 grid which is in between the other two oc-
cupied corners towards the external row or column, arbitrarily. The case where the
minimal wrapping grid has dimension 4
×
×
4 is obtained and no corners are occupied.
13.4 Gathering on Trees
In this section, gathering results on trees are presented. To the best of our knowl-
edge, these are original contributions as trees were never treated before under the
considered model. Given a tree, a node at minimal distance from all the other ones
is called
center
. Based on well-known results [
28
] about the tree topology, within
a tree there is either one center or there are two neighboring centers. In the former
case, no matter the initial distribution of the robots, each of them can move towards
the center, concurrently. The gathering will be eventually finalized, even without any
multiplicity detection assumption. In the latter case, some more specific arguments
are required. In fact, some impossibility results hold.
Lemma 2.
If the two subtrees rooted at the centers along with the disposal of the
robots are isomorphic, then the gathering is impossible.
Proof.
Any algorithm designed to accomplish the gathering on the tree must work
regardless the delays on the decisions made by robots. In particular, also the syn-
chronous case must be solved. Since the two considered subtrees are isomorphic,
with the same disposal of robots, if one robot is allowed to move within one sub-
tree, there must exist another robot that is allowed to accomplish the same specular
movement. If both robots perform such movements, again a configuration with two
isomorphic subtrees is obtained. In proceeding so, there will not exist any move that
can break such a situation. Hence, the gathering cannot be finalized as it requires to
distinguish one single node belonging to one of the two subtrees.
In the case the isomorphism among the two subtrees along with the disposal of
the robots does not hold, the following strategy can be applied. Let
c
1
and
c
2
be
the two centers of the input tree
T
,andlet
T
1
and
T
2
be the two subtrees rooted
at
c
1
and
c
2
, respectively, when the edge connecting
c
1
and
c
2
is removed. If the
number of nodes occupied in
T
1
is smaller than that in
T
2
, then all robots in
T
1
are
moved towards
c
2
.Once
T
1
gets empty, all robots in
T
2
should be moved towards
Search WWH ::
Custom Search