Information Technology Reference
In-Depth Information
When the starting configuration does not belong to the above ungatherable
configurations, it always possible to devise an algorithm achieving the gathering
without multiplicity detection.
The idea is to distinguish between the two nodes that are the central nodes of
the odd borders of the grid. If
m
(
n
, respectively) is odd, then the two mentioned
nodes are given by positions
M
,
2
]
,
2
]
[
2
,
[
2
,
,
respectively). The line connecting those two nodes will be denoted as the
NS
line.
One of the two extreme nodes on the
NS
line will be the place where the gathering
is finalized. In order to select the gathering node, a robot considers the line passing
through the central edges of the even sides of the grid (denoted as the
EW
line)
dividing the grid into two halves. The idea is to distinguish a north and a south
part among the two halves and the gathering node will be the one in the north half.
See Fig.
13.6
a for a visualization. The north is the half with more nodes occupied
by robots, if any. If the number of occupied nodes in the two halves is the same,
then some more computations are required. In both cases, the robots move from the
south to the north until all the robots will be in the north part. Note that, during such
a stage, if multiplicities are created in the south, then the number of occupied nodes
decreases with respect to the north part. If multiplicities are created in the north, it
means that a robot has moved from the south to the north part, still preserving the
required distinction.
In order to distinguish the north from the south in the case of configurations with
the same number of robots among the two halves obtained by the
EW
line, a robot
associates to each configuration
C
a binary string as follows. Starting from each
corner of the grid, and proceeding in the direction parallel to the
NS
line, a robot
records the elements of
M
row by row, or column by column (according to the di-
rection specified by the
NS
line). Once it has computed the four strings, it associates
to
C
the lexicographically largest one. For instance, starting from corner
M
[
1
and
M
[
n
(
M
1
]
and
M
m
]
,
and assuming
m
odd, the corresponding binary string would be composed by the se-
quence
M
[
1
,
1
]
[
,
]
[
,
]
...
[
,
]
[
,
]
...
[
,
]
[
,
]
...
[
,
]
1
1
,
M
2
1
,
,
M
n
1
,
M
1
2
,
,
M
n
2
,
M
1
m
,
,
M
n
m
.See
Fig.
13.6
a for an example.
It is possible to show that if
C
is a gatherable configuration, then, among the four
possible strings coming from a robot view of the input grid, at most two strings
can be the lexicographically largest ones. If there are two largest strings, then they
represent the views of
C
starting from two symmetric corners with respect to the
NS
line, see Fig.
13.6
d. Note that, instances of Fig.
13.6
b, c are ungatherable as they
admit an edge-edge symmetry or a periodicity.
Then, the
gathering node
is defined as the one residing on the same odd side
where the corner(s) providing the lexicographically largest string resides. The gath-
ering node will determine also the directions along the
NS
line: the gathering node
is called the north pole.
Configurations on odd
even grids that are aperiodic and do not admit an axis
of symmetry passing through edges are always gatherable, and the algorithm is the
following.
×
Search WWH ::
Custom Search