Routing Directions: Keeping it Fast and Simple

The problem of providing meaningful routing directions over road networks is of great importance. In many real-life cases, the fastest route may not be the ideal choice for providing directions in written/spoken text, or for an unfamiliar neigh-borhood, or in cases of emergency. Rather, it is often more preferable to offer \simple " directions that are easy to mem-orize, explain, understand or follow. However, there exist cases where the simplest route is considerably longer than the fastest. This paper tries to address this issue, by nd-ing near-simplest routes which are as short as possible and near-fastest routes which are as simple as possible. Partic-ularly, we focus on efficiency, and propose novel algorithms, which are theoretically and experimentally shown to be sig-ni cantly faster than existing approaches. Categories and Subject Descriptor