Constructing approximate shortest path maps in three dimensions

Research output: Contribution to conferencePaperpeer-review

Abstract

A new technique for constructing a data-structure that approximates shortest path maps in Rd is discussed. An algorithm that computes a subdivision of P of size O((n/ε)log(1/ε)) which can be used to answer efficiently approximate shortest path queries is introduced. An algorithm that computes a subdivision of R3, which can be used to answer efficiently approximate shortest path queries is presented.

Original languageEnglish (US)
Pages383-391
Number of pages9
DOIs
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA
Duration: Jun 7 1998Jun 10 1998

Other

OtherProceedings of the 1998 14th Annual Symposium on Computational Geometry
CityMinneapolis, MN, USA
Period6/7/986/10/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Constructing approximate shortest path maps in three dimensions'. Together they form a unique fingerprint.

Cite this