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 [6] 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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/3-540-44634-6_27
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