zbMATH — the first resource for mathematics

I/O-efficient map overlay and point location in low-density subdivisions. (English) Zbl 1193.68276
Tokuyama, Takeshi (ed.), Algorithms and computation. 18th international symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77118-0/pbk). Lecture Notes in Computer Science 4835, 500-511 (2007).
Summary: We present improved and simplified 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({\text{sort}}(n))\) I/O’s into a compressed linear quadtree such that one can:
\(\bullet\) compute the overlay of two preprocessed subdivisions in \(O({\text{scan}}(n))\) I/O’s, where \(n\) is the total number of edges in the two subdivisions,
\(\bullet\) answer a single point location query in \(O(\log _{B } n)\) I/O’s and \(k\) batched point location queries in \(O({\text{scan}}(n) + {\text{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.
For the entire collection see [Zbl 1136.68011].

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P05 Data structures
68W05 Nonnumerical algorithms
68W40 Analysis of algorithms
PDF BibTeX Cite
Full Text: DOI