We consider the problem of rendezvous between two robots exploring an unknown environment. That is, how can two autonomous exploring agents that cannot communicate with one another over long distances meet if they start exploring at different locations in an unknown environment. The intended application is collaborative map exploration. Ours is the first work to formalize the characteristics of the rendezvous problem, and we approach it by proposing several alternative algorithms that the robots could use in attempting to rendezvous quickly while continuing to explore. The algorithms are based on the assumption that potential rendezvous locations, called landmarks, can be selected by the robots as they explore; these locations are based on a distinctiveness measure computed with an arbitrary sensor. We consider the performance of our proposed algorithms analytically with respect to both expectedand worst-case behaviour. We then examine their behaviour under a wider set of conditions in simulation.