3.3 Spreading Algorithm for Piecewise Linear Regions

 The problem of spreading of robots over any region boils down to the mathematical

paradigm whether a point is inside a curve or not. The solution for this problem can be

very complex depending of the arbitrary shape of the curve and a general analytic

solution is not known. But if it can be assumed that any curve can be sufficiently

approximated with a piece-wise linear curve, then the solution is given by a very simple

theorem called Jordan curve theorem [Fra02].

 Unlike the spreading algorithm for circular region, the above solution warrants the

robots to know their own absolute position as well as the position of the vertices of the

curve to spread themselves inside the given region. Since this is the simplest way to

implement spreading over any piecewise linear region, the increase in cost due to the

above requirement may be compromised.

3.3.1 Jordan Curve Theorem

 A semi-infinite ray going out in any direction from the testing point (figure 3.10)

will cross the edges of the curve odd number of times if the point is inside the curve and

even number of times if the point is outside the curve. At each crossing, the ray switches

between inside and outside. This theorem is true for any closed curve, whether it is

convex or concave.


Figure 3.10 Jordan curve theorem