Constructing approximate shortest path maps in three dimensions

Research output: Contribution to conferencePaper

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
StatePublished - Jan 1 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

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Cite this

Har-Peled, S. (1998). Constructing approximate shortest path maps in three dimensions. 383-391. Paper presented at Proceedings of the 1998 14th Annual Symposium on Computational Geometry, Minneapolis, MN, USA, .