While in the latter scenario the relative movement of the agents depends only on their routes, in our setting, this movement is also controlled by the adversary. 

Agents with routes R 1 and R 2 and with walks f 1 and f 2 meet at time t , if points f 1 ( t ) and f 2 ( t ) are identical. A rendezvous is guaranteed for routes R 1 and R 2 , if the agents using these routes meet at some time t , regardless of the walks chosen by the adversary. A rendezvous algorithm executed by agents in a graph or in a terrain produces routes of agents, given the label of each agent and its starting point. 

It should be stressed that, while routes of agents are formally defined as infinite sequences of segments, our results imply that in any instance of the rendezvous problem, meeting will occur at some finite time, and thus each agent will compute only finitely many seg- ments of its route. As mentioned above, agents compute their routes in stages, and given any walk chosen by the adversary, each stage is completed in finite time. There is no stopping issue in our solution: rendezvous always occurs at some stage for each of the agents and then both agents stop. Another feature of our rendezvous algorithms is that in the choice of consecutive segments of its route an agent does not use the knowledge of the walk to date. Thus the route depends only on the label of the agent, on the environment (graph or terrain), and on the starting point chosen by the adversary, but not on its other actions. 

Our results. We give two deterministic algo- rithms, the first for rendezvous in the graph scenario and the second in the geometric scenario. For the graph scenario, our algorithm accomplishes rendezvous in any connected countable ∗ (finite or infinite) graph, for arbi- trary starting nodes. A consequence of this very general result is the positive answer to the following question from [12]: Is deterministic asynchronous rendezvous fea- sible in any finite connected graph without knowing any upper bound on its size? (In [12] the authors presented a deterministic asynchronous rendezvous algorithm in ar- bitrary finite connected graphs with known upper bound on the size.) 

For the geometric scenario, our algorithm accom- plishes rendezvous for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. (Recall that a subset T of the plane is path-connected, if for any points u, v ∈ T , there is a continuous function h : [0 , 1] −→ P , such that P ⊆ T and h (0) = u , h (1) = v .) On the other hand, our algorithm guarantees the following approxi- mate rendezvous for agents starting at arbitrary interior 

points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other. This implies the perhaps surprising result that if agents have arbitrarily small positive visibility ranges (rather than 0 visibility range as we assume) and they start in arbitrary points of the (empty) plane, then they will see each other in finite time, regardless of the actions of the adversary. 

Discussion of limitations. While our algorithms work in a very general setting – agents can, indeed, meet almost everywhere – it turns out that none of the few limitations imposed on the environment can be removed. For the graph scenario, the only limitation is connectivity of the graph. It is clear that rendezvous in disconnected graphs is impossible, if the agents start in different connected components. For the geometric scenario, let us review the limitations one by one. First, we assume that the terrain is closed. This assumption cannot be entirely removed for the following technical reason. Consider the construction of a route in an open disc. An agent starting at any point, that chooses in the first stage an arbitrary direction and a sufficiently large distance, at some point would have to leave the disc. Since it does not see anything in its vicinity, it cannot know where the boundary is before hitting it, and it cannot hit it, as it is not allowed to leave the terrain. It follows that the agent could not construct further segments of its route. The second assumption is that agents start at interior points of the terrain. This assumption cannot be removed either. Indeed, suppose that the terrain is a closed disc with a semi- circle attached to it. This is a closed subset of the plane with nonempty path-connected interior. Suppose that one agent starts in the disc and the other at the end of the semi-circle. Since agents need to move along polygonal lines, the second agent could not move at all and the first one cannot reach it. Our next assumption is that the interior of the terrain is path-connected. To show that this assumption cannot be removed, consider two disjoint closed discs joined by an arc of a circle. This terrain is closed and path-connected, but if each agent starts inside a different disc, again they cannot meet, because agents need to move along polygonal lines, and hence cannot traverse the joining arc. The final assumption is that the starting points of the agents have rational coordinates. In Section 4 we prove that if the agents start in arbitrary points, then rendezvous cannot be guaranteed even in the plane. We show, however, that for arbitrary starting points approximate rendezvous is guaranteed. 

Related work. The rendezvous problem was first described in [25]. A detailed discussion of the large literature on rendezvous can be found in the excellent 

