Querying approximate shortest paths in anisotropic regions

Siu Wing Cheng*, Hyeon Suk Na, Antoine Vigneron, Yajun Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let p ≤ 1 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/p. Different convex distance functions may be used for different faces, and obstacles are allowed. Let e be any number strictly between 0 and 1. Our data structure returns a (1 + e) approximation of the shortest path cost from the fixed source to a query destination in 0(log) time. Afterwards, a (1 + ε)-approximate shortest path can be reported in 0(log n) time plus the complexity of the path. The data structure uses 0(log)space and can be built in 0((log))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.

Original languageEnglish (US)
Pages (from-to)1888-1918
Number of pages31
JournalSIAM Journal on Computing
Volume39
Issue number5
DOIs
StatePublished - Feb 25 2010

Keywords

  • Anisotropic regions
  • Approximation algorithms
  • Convex distance functions
  • Shortest path

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this