ABSTRACT

Proving that an interval i will not adjoin more than two cells is also shown by contradiction. First, assume i is a vertical interval in Cnew adjacent to two existing cells. The two cells (Ca and Cb, complete or incom­ plete) must therefore be unattached on the side facing Cnew Ca and Cb must therefore have attached floors and ceilings (including their mutual edge), and both must therefore have been created by a robot with the same sweep direction. But this is not possible, as one would have to be created first (even if both came from different robots), and would therefore have to extend to a true wall, not just to the other cell. Two cells like this Ca and Cb therefore cannot exist, and so a verti­ cal interval cannot have more than one neighbor. For a horizontal interval, the argument works exactly the same way for complete cells. However, in this case it is possible to have at most two incomplete cells adjacent to i if and only if they are Co and C\.