I/O-efficient shortest path queries in geometric spanners

Abstract. 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.