The Ruby is found on Mountain Peaks. After you have recruited both Medea and Gracie to help you, Medea states you can find the ruby there. Simply go back to the overworld and hit explore to make the new area appear. From there, get the ruby, talk to Medea again and meet up at the edge to cross.
