coordinates in the system Σ$_{v}$, at distance less than r from w . Let P$_{v}$ be the polygonal line P extended by the segment w ′ w ′′ . Note that P$_{v}$ is at distance at least r from the boundary of T . Indeed, if x ∈ P , then the distance from x to the boundary is at least d > r , and if x ∈ w ′ w ′′ , then the distance from x to the boundary is at least ρ/ 2 ≥ r , as the entire segment w ′ w ′′ is included in disc D . 

Let Φ be the translation by the vector ( w $^{′′}$w ) and let P$_{w}$ be the image of P$_{v}$ with respect to Φ. The point w is one of the extremities of P$_{w}$ . Since the distance from w ′′ to w is less than r , the entire polygonal line P$_{w}$ is in the interior of T . The polygonal line P$_{w}$ is rational in the system Σ$_{w}$. 

Let f be any walk of the first agent on any route with the initial part P$_{v}$ starting at v , and let g be any walk of the second agent on any route with the initial part P$_{w}$ starting at w . Consider the composition g ∗ = Φ − 1 ◦ g . Hence g ∗ is a walk on a route with initial part P$_{v}$ , starting at w $^{′′}$. By Theorem 4.1, Algorithm GeometricRV guarantees rendezvous of agents at some point in time t , for the walk f starting at v and the walk g ∗ starting at w $^{′′}$. 

Consider the positions at time t of both agents starting at v and w , in walks f and g . Since f ( t ) = g $^{∗}$( t ) = Φ − $^{1}$( g ( t )), and Φ is a translation by a vector of length less than r (hence less than ϵ ), it follows that the distance between f ( t ) and g ( t ) is less than ϵ . Since walks f and g were arbitrarily chosen by the adversary, this guarantees ϵ -approximate rendezvous. 

A consequence of Theorem 4.2 is that if agents have arbitrarily small positive visibility ranges (rather than 0 visibility range as we assumed) and they start in arbitrary points of the (empty) plane, then Algorithm GeometricRV guarantees that they will see each other in finite time, regardless of the actions of the adversary. 

## 5 Conclusion 

We provided deterministic asynchronous rendezvous algorithms for graphs and for terrains in the plane. We studied only the feasibility of rendezvous and our results are very general: for the graph scenario, we showed that rendezvous is possible in any connected countable (finite or infinite) graph, starting from any nodes, without any information on the graph. The only thing an agent needs to know is its own label. In particular, this result implies a positive solution of a problem from [12]. 

Our algorithms rely on an arbitrary fixed enumera- tion of quadruples ( i, j, s $^{′}$, s$^{′′}$), where i and j are positive integers and s ′ and s ′′ are finite sequences of positive in- tegers. The complexity of the algorithm (measured by the worst-case length of paths that the agents have to 

traverse until rendezvous) depends on this enumeration, but we do not think any enumeration can make the al- gorithm efficient. Thus a natural interesting question left for further investigations is the following: 

Does there exist a deterministic asyn- chronous rendezvous algorithm, working for all connected countable unknown graphs, with complexity polynomial in the labels of the agents and in the initial distance between them? 

## References 

[1] R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lov´ asz, and C. Rackoff, Random walks, universal traversal se- quences, and the complexity of maze problems, Proc. Annual Symposium on Foundations of Computer Sci- ence FOCS’1979, 218-223. 

[2] S. Alpern, The rendezvous search problem, SIAM J. on Control and Optimization 33 (1995), 673-683. 

[3] S. Alpern, Rendezvous search on labelled networks, Naval Reaserch Logistics 49 (2002), 256-274. 

[4] S. Alpern and S. Gal, The theory of search games and rendezvous. Int. Series in Operations research and Management Science, number 55, Kluwer Academic Publishers, 2002. Kluwer Academic Publisher, 2002. 

[5] J. Alpern, V. Baston, and S. Essegaier, Rendezvous search on a graph, Journal of Applied Probability 36 (1999), 223-231. 

[6] E. Anderson and R. Weber, The rendezvous problem on discrete locations, Journal of Applied Probability 28 (1990), 839-851. 

[7] E. Anderson and S. Fekete, Asymmetric rendezvous on the plane, Proc. 14th Annual ACM Symp. on Computational Geometry, 365-373, 1998. 

[8] E. Anderson and S. Fekete, Two-dimensional ren- dezvous search, Operations Research 49 (2001), 107- 118. 

[9] V. Baston and S. Gal, Rendezvous on the line when the players’ initial distance is given by an unknown probability distribution, SIAM J. on Control and Op- timization 36 (1998), 1880-1889. 

[10] V. Baston and S. Gal, Rendezvous search when marks are left at the starting points, Naval Res. Log. 48 (2001), 722-731. 

[11] M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Solving the Robots Gathering Problem, Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), 1181-1196. 

[12] G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro, Asynchronous deterministic ren- dezvous in graphs, Theoretical Computer Science 355 (2006), 315-326. 

[13] D. Coppersmith,, P. Doyle, P. Raghavan, and M. Snir, Random walks on weighted graphs, and applications to 

