We present improved and simplified
I/O{\textsc{i/o}}
-efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely,
we show how to preprocess a low-density subdivision with
n edges in
O(sort(n))O({\mathit{sort}}(n))
i/o’s into a compressed linear quadtree such that one can:
| •
|
compute the overlay of two preprocessed subdivisions in
O(scan(n))O({\mathit{scan}}(n))
i/o’s, where n is the total number of edges in the two subdivisions,
|
| •
|
answer a single point location query in O(log
B
n) i/o’s and k batched point location queries in
O(scan(n) + sort(k))O({\mathit{scan}}(n) + {\mathit{sort}}(k))
i/o’s.
|
For the special case where the subdivision is a fat triangulation, we show how to obtain the same bounds with an ordinary
(uncompressed) quadtree, and we show how to make the structure fully dynamic using O(log
B
n) i/o’s per update. Our algorithms and data structures improve on the previous best known bounds for general subdivisions both
in the number of i/o’s and storage usage, they are significantly simpler, and several of our algorithms are cache-oblivious.
MdB and ST were supported by the Netherlands’ Organisation for Scientific Research (NWO).