Querying approximate shortest paths in anisotropic regions

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let be any number strictly between 0and 1. Our data structure returns a (1+)approximation of the shortest path cost from the fixed source to a querydestination in O(logn/) time. Afterwards, a(1+)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O( 2 n4/2 log n/) space and can be built in O((2 n4)/(2)(log n/)2) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Pages84-91
Number of pages8
DOIs
StatePublished - Oct 22 2007
Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
Duration: Jun 6 2007Jun 8 2007

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other23rd Annual Symposium on Computational Geometry, SCG'07
CountryKorea, Republic of
CityGyeongju
Period06/6/0706/8/07

Keywords

  • Computational geometry
  • Data structures
  • Shortest path

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Cite this