I/O-efficient dynamic point location in monotone planar subdivisions
View/ Open
Issue Date
1999Author
Agarwal, Pankaj K.
Arge, Lars
Brodal, Gerth Stølting
Vitter, Jeffrey Scott
Publisher
Society for Industrial and Applied Mathematics
Type
Article
Article Version
Scholarly/refereed, publisher version
Metadata
Show full item recordAbstract
We present an efficient external-memory dynamic data structure for point location in monotone planar subdivisions. Our data structure uses O(N/B) disk blocks to store a monotone subdivision of size N, where B is the size of a disk block. It supports queries in O(logi N) I/OS (worst-case) and updates
in O(lo& N) I/OS (amortized). We also propose a new variant of B-trees, called leuelbalanced
B-trees, which allow insert, delete, merge, and split
operations in O((l+ $ logM,B f) log, N) I/OS (amortized), 2 5 b 2 B/2, even if each node stores a pointer to its parent. Here M is the size of main memory. Besides being essential to our point-location data structure, we believe that
level-balanced B-trees are of significant independent interest. They can, for example, be used to dynamically maintain a planar St-graph using O((1 + $10g~,~ $$) log, N) = O(logi N) I/OS (amortized) per update, so that reachability queries can be answered in O(log, N) I/OS (worst case).
Collections
Citation
P. K. Agarwal, L. Arge, G. Brodal, and J. S. Vitter. “I/O-Efficient Dynamic Point Location in Monotone Subdivisions,” Proceedings of the 10th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’99), Baltimore, MD, January 1999, 11–20. http://doi.acm.org/10.1145/314500.314525
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.