unknown terrain T designs a route in the corresponding unknown graph G$_{T}$ as follows. When the agent chooses a port at a node p ∈ V 1 , this edge corresponds to some rational point q$_{i}$ in the plane that the agent tries to reach from p . Two cases may occur. The agent either walks in the interior of T until reaching q$_{i}$ , which corresponds to the traversal of an edge between two nodes of V 1 , or it hits the boundary of T , which corresponds to a visit of a node p ′ ∈ V 2 . At a node p ′ ∈ V 2 there is no choice of port, since its degree is 1. The agent takes the unique port which leads to the (already visited) node p ∈ V 1 . The resulting route is a sequence of segments joining rational interior points of the terrain T and of pairs of consecutive segments ( vb, bv ), where v is a rational interior point of T and b is a point on the boundary of T . Since by Lemma 4.1 graph G$_{T}$ is connected, ren- dezvous is guaranteed in the graph G$_{T}$ , which implies rendezvous in T . Theorem 4.1. Algorithm GeometricRV guarantees asynchronous rendezvous for arbitrary two agents starting from arbitrary rational interior points of any closed terrain T with path-connected interior. Theorem 4.1 should be contrasted with the follow- ing negative result showing that the restriction on the starting points of the agents cannot be removed, even for rendezvous in the (empty) plane. Proposition 4.1. There is no algorithm that guaran- tees asynchronous rendezvous of arbitrary agents start- ing from arbitrary points in the plane. Proof. Consider the agent with label ℓ operating in the empty plane. Since the terrain is fixed, the route of this agent depends only on the starting point. Let R = ( e 1 , e 2 , ... ) be the route of the agent with label 1 starting at a fixed point v . Consider the route R 2 ( w ) of the agent with label 2 starting at point w . Since there are no boundary points in the terrain, for any starting points w ′ and w $^{′′}$, route R 2 ( w $^{′′}$) is a parallel shift of route R 2 ( w $^{′}$) by the vector ( w $^{′}$, w$^{′′}$). Both of them are polygonal lines. We will say that two routes are almost disjoint if all vertices of each of them are outside the other route. Observe that if, for some starting point w , route R 2 ( w ) of agent 2 is almost disjoint from route R of agent 1, then the adversary can avoid rendezvous of agents 1 and 2 following these routes, by first moving agent 1 to the end of the first segment of its route, then moving agent 2 to the end of the first segment of its route and so on, alternating traversals of agents on consecutive segments of their routes. Hence, in order to prove our result, it is Proof. Fix an ϵ > 0. Consider any two agents starting at interior points v and w of the terrain T . Let ρ > 0 be the distance from w to the boundary of T . Choose a point w ′ with rational coordinates in Σ$_{v}$, in the interior of the disc D of radius ρ/ 2 centered at w . By Lemma 4.1 (applied to the system Σ$_{v}$ instead of Σ), there exists a rational polygonal line P in the system Σ$_{v}$, included in the interior of T and joining v and w $^{′}$. Let d > 0 be the distance between P and the boundary of T . Let r = min( ρ/ 2 , d/ 2 , ϵ ). Choose a point w ′′ with rational While Proposition 4.1 shows that rendezvous of agents starting from arbitrary points is impossible, it turns out that a slightly easier task can be accomplished in this setting. For any ϵ > 0, we say that routes R 1 and R 2 of agents guarantee ϵ - approximate rendezvous , if at some point t of time, the agents get at distance at most ϵ from each other, regardless of the walks chosen by the adversary. Theorem 4.2. Algorithm GeometricRV guarantees ϵ - approximate rendezvous for any ϵ > 0 , for arbitrary agents starting from arbitrary interior points of any closed terrain T with path-connected interior. The intersection of all discs D$_{k}$ is non-empty. Let w ∗ be a point in this intersection. Since ( p 1 , p 2 , . . . ) enumerated all couples ( e$_{i}$, f$_{j}$ ), it follows that route R 2 ( w $^{∗}$) is almost disjoint from route R , and hence agents 1 and 2 starting at points v and w $^{∗}$, respectively, do not meet for some walks chosen by the adversary. Let ( f 1 , f 2 , ... ) be the sequence of vectors corre- sponding to consecutive segments of the route R 2 ( w ), for any starting point w . For any fixed point w , de- note by f$_{j}$ ( w ) the segment corresponding to vector f$_{j}$ on route R 2 ( w ). Let ( p 1 , p 2 , . . . ) be any sequence that orders all couples ( e$_{i}$, f$_{j}$ ), for all positive integers i, j . For any k , let p$_{k}$ = ( e$_{i}$$_{k}$, f$_{j}$$_{k}$ ) We will construct by induc- tion a descending sequence of closed discs ( D 1 , D 2 , . . . ) of positive radii, satisfying the following invariant. For all points w ∈ D$_{k}$ , both endpoints of the segment e$_{i}$$_{k}$ are outside of the segment f$_{j}$$_{k}$ ( w ) and both endpoints of the segment f$_{j}$$_{k}$ ( w ) are outside of the segment e$_{i}$$_{k}$ . Suppose that the invariant is satisfied for k − 1 (for k = 1 we may take as D 0 any disc with radius 1). The set of points w inside disc D$_{k}$$_{−}$ 1 that may possibly violate the invariant for k is contained in the union of four segments: two seg- ments parallel to f$_{j}$$_{k}$ and two segments parallel to e$_{i}$$_{k}$ . There exists a closed disc of positive radius contained in D$_{k}$$_{−}$ 1 which is disjoint from those four segments. Let D$_{k}$ be such a disc. Thus the invariant is satisfied for k . This completes the construction by induction. enough to show the existence of a point w $^{∗}$, such that route R 2 ( w $^{∗}$) is almost disjoint from route R .