Proof. Let v and i (resp. w and j ) be the starting node and the label of the first agent (resp. the second agent). There exists a path q linking v to w , since the graph G is connected. Let s ′ (resp. s $^{′′}$) be the finite sequence of ports corresponding to the path q (resp. the path q ). In view of Proposition 2.1, it suffices to prove that the routes of the two agents form a tunnel. We show that, after the phase corresponding to the quadruple ϕ$_{k}$ = ( i, j, s $^{′}$, s$^{′′}$) during the execution of Algorithm GraphRV for agents i and j , the routes of the two agents form a tunnel. Observe that this phase eventually occurs during any execution of GraphRVREC , since all recursive calls of any phase k ′ < k are done with a parameter p strictly smaller than k $^{′}$. Thus all these phases are completed in finite time. First, we show by induction that, at the beginning of phase k of any execution of Algorithm GraphRV , each agent is at its starting node. This is clearly true for k = 1. Assume that the property holds for k − 1. It follows that during the execution of the phase k − 1, the paths r$_{hist}$ and r$_{sim}$ are cycles. Hence, after the execution of line 16, the agent ends in node w . After the execution of line 17, the agent returns to the starting node v of the phase k − 1. So, the agent starts phase k in the same node, and the property is true for all k . Let r$_{v}$ (resp. r$_{w}$ ) be the output of the execution of the first k − 1 phases of Algorithm GraphRV for agent i (resp. j ) starting in node v (resp. w ). At the beginning of phase k , the portion of the route constructed by agent i is r$_{v}$ . After the execution of line 12, the portion of the route constructed by agent i is r$_{v}$ ⌢ q , since the agent has started the phase in node v . The path r$_{sim}$ computed by the recursive call of GraphRVREC is equal to r$_{w}$ . It follows that at the end of phase k , the portion of the route constructed by agent i is ρ = r$_{v}$ ⌢ q ⌢ r$_{w}$ ⌢ q ⌢ r$_{v}$ ⌢ q ⌢ r$_{w}$ ⌢ q . Similarly, at the end of phase k , the portion of the route constructed by agent j is ρ ′ = r$_{w}$ ⌢ q ⌢ r$_{v}$ ⌢ q ⌢ r$_{w}$ ⌢ q ⌢ r$_{v}$ ⌢ q . By construction, the part r$_{v}$ ⌢ q ⌢ r$_{w}$ ⌢ q ⌢ r$_{v}$ ⌢ q ⌢ r$_{w}$ of ρ and the part r$_{w}$ ⌢ q ⌢ r$_{v}$ ⌢ q ⌢ r$_{w}$ ⌢ q ⌢ r$_{v}$ of ρ ′ form a tunnel (see Fig 1). In this section we consider the problem of rendezvous in a terrain included in the Euclidean plane. As announced in the introduction, we restrict attention to closed subsets of the plane whose interior is path-connected. We observed that these restrictions cannot be removed. Fix a system of coordinates Σ with the y -axis pointing to North (shown by compasses of the agents) and with the unit of length equal to that of the agents. Points with rational coordinates in Σ will be called rational . A polygonal line all of whose vertices, The algorithm is a direct application of Algorithm GraphRV to the graph G$_{T}$ . The agent operating in an For each pair of points p 1 , p 2 , such that p 1 ∈ V 1 and p 2 is any rational point of the plane, we consider the segment s = p 1 p 2 . If s does not intersect the boundary of T , then p 2 must belong to V 1 and we add the edge { p 1 , p 2 } to E . If s intersects the boundary of T , we add a new node v to V 2 and we add the edge { p 1 , v } to E . Note that such a node v is always added to V 2 when point p 2 is on the boundary of T or outside of T (and it may or may not be added to V 2 when p 2 is in the interior of T ). Since each node in V 2 corresponds to a pair of rational points p 1 , p 2 , there is a countable number of nodes in V 2 , each of them having degree 1. The unique port at any node in V 2 has number 1 and ports at any node in V 1 are defined as follows. Let ( z 1 , z 2 , . . . ) be any fixed enumeration of all pairs of rational numbers. Let z$_{i}$ = ( q 1 , q 2 ). Let u be the point in the plane with coordinates ( q 1 , q 2 ) in the system Σ$_{p}$. The port at p corresponding to edge { p, u } has number i . We define the following graph G$_{T}$ = ( V, E ), for a given terrain T . The set of nodes V is the union of two disjoint subsets V 1 , V 2 . The set V 1 is the set of all interior, rational points of T and the set V 2 is defined below. Lemma 4.1. In any path-connected, open subset S of the plane and for any rational points u, v ∈ S , there exists a rational polygonal line included in S , with extremities u and v , all of whose vertices are rational. Proof. By path-connectivity of S , there exists a path p included in S with extremities u and v , which is a continuous image of the interval [0 , 1]. Let d be the distance from p to cS - the complement of S . Since p ∩ cS =  and both p and cS are closed sets, we have d > 0. Partition the plane into squares of side length at most d/ 2 with rational vertices. Let Q be the set of squares intersecting p . Since p is a bounded set, Q is finite. Consider the graph G$_{p}$ with node set Q , such that x, y ∈ Q are adjacent if p contains a point belonging to a common boundary of x and y . Since G$_{p}$ is connected, there exists a path ( x 1 , . . . , x$_{k}$ ) in G$_{p}$ linking squares x 1 containing u and x$_{k}$ containing v . Let p ∗ be the polygonal path ( uw 1 , w 1 w 2 , . . . , w$_{k}$$_{−}$ 1 w$_{k}$, w$_{k}$v ), where w$_{i}$ is the center of square x$_{i}$ , for all i = 1 , . . . , k . The path p ∗ is rational and contained in the union of squares from Q . Since each point of p ∗ is at distance at most $_{d}$√$_{2}$$_{/}$$_{2 from some point of}$ p , we have p ∗ ∩ cS =  , hence p ∗ is included in S . including extremities, are rational will be called a rational line . For any point u , let Σ$_{u}$ be the shift of the system Σ with origin at point u . Algorithm GeometricRV 4 Rendezvous in the geometric scenario