Almost optimal distance oracles for planar graphs

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the naïve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space O ( n 1+є ) and query-time Õ(1) for any constant є>0, (ii) an oracle with space Õ( n ) and query-time O ( n є ) for any constant є>0, and (iii) an oracle with space n 1+ o (1) and query-time n o (1) .

Authors

• Panagiotis Charalampopoulos
• Pawel Gawrychowski
• Shay Mozes
• Oren Weimann

Keywords

• Voronoi diagrams
• distance oracles
• planar graphs
• shortest paths