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 language | English (US) |
|---|---|
| Pages | 383-391 |
| Number of pages | 9 |
| DOIs | |
| State | Published - 1998 |
| Externally published | Yes |
| Event | Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998 |
Other
| Other | Proceedings of the 1998 14th Annual Symposium on Computational Geometry |
|---|---|
| City | Minneapolis, MN, USA |
| Period | 6/7/98 → 6/10/98 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics