×

Querying approximate shortest paths in anisotropic regions. (English) Zbl 1207.68415

Summary: We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let \(\rho\geqslant1\) be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius \(1/\rho\). Different convex distance functions may be used for different faces, and obstacles are allowed. Let \(\varepsilon\) be any number strictly between 0 and 1. Our data structure returns a \((1+\varepsilon)\)-approximation of the shortest path cost from the fixed source to a query destination in \(O(\log\frac{\rho n}{\varepsilon})\) time. Afterwards, a \((1+\varepsilon)\)-approximate shortest path can be reported in \(O(\log n)\) time plus the complexity of the path. The data structure uses \(O(\frac{\rho^2n^3}{\varepsilon^2}\log\frac{\rho n}{\varepsilon})\) space and can be built in \(O(\frac{\rho^2n^3}{\varepsilon^2}(\log\frac{\rho n}{\varepsilon})^2)\) time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI