Important drawbacks of map-based navigation applications for mobile phones are their small screen size and that users have to associate the information provided by the mobile phone with the real word. Therefore, we designed, implemented and evaluated the Rotating Compass - a novel public display for pedestrian navigation. Here, a floor display continuously shows different directions (in a clockwise order) and the mobile phone informs the user when their desired direction is indicated. To inform the user, the mobile phone vibrates in synchronization with the indicated direction. We report an outdoor study that compares a conventional paper map, a navigation application running on a mobile device, navigation information provided by a public display, and the Rotating Compass. The results provide clear evidence of the advantages of the new interaction technique when considering task completion time, context switches, disorientation events, usability satisfaction, workload and multi-user support.