I/O-efficient shortest path queries in geometric spannersPublic Deposited
Downloadable ContentDownload PDF
- Resource Type
We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell” spanner of  for point sets in higher dimensions. As important ingredients to our algorithms, we present I/O efficient algorithms to color the vertices of a graph of bounded degree, answer binary search queries on topology buffer trees, and preprocess a rooted tree for answering prioritized ancestor queries.
- Maheshwari, A, Smid, M, & Zeh, N. (Norbert). (2001). I/O-efficient shortest path queries in geometric spanners. doi:10.1007/3-540-44634-6_27
- Date Created
- In Collection: