Efficient Algorithms for Geometric Shortest Path Query Problems

Danny Z. Chen ()
Additional contact information
Danny Z. Chen: University of Notre Dame, Department of Computer Science and Engineering

A chapter in Handbook of Combinatorial Optimization, 1998, pp 747-779 from Springer

Abstract: Abstract Computing shortest paths in a geometric environment is a fundamental topic in computational geometry and finds applications in many other areas. The problem of processing geometric shortest path queries is concerned with constructing an efficient data structure for quickly answering on-line queries for shortest paths connecting any two query points in a geometric setting. This problem is a generalization of the well-studied problem of computing a geometric shortest path connecting only two specified points. This paper covers the newly-developed algorithmic paradigms for processing geometric shortest path queries and related problems. These general paradigms have led to efficient techniques for designing algorithms and data structures for processing a variety of queries on exact and approximate shortest paths in a number of geometric and graphical settings. Some open problems and promising directions for future research are also discussed.

Keywords: Short Path; Planar Graph; Query Point; Steiner Point; Path Query (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-0303-9_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461303039

DOI: 10.1007/978-1-4613-0303-9_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().