Loading...
I/O-efficient dynamic point location in monotone planar subdivisions
Agarwal, Pankaj K. Arge, Lars Brodal, Gerth Stølting Vitter, Jeffrey Scott
Agarwal, Pankaj K.
Arge, Lars
Brodal, Gerth Stølting
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
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).
Description
Date
1999
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Files
Loading...
Vitter_1999.pdf
Adobe PDF, 1.22 MB
Research Projects
Organizational Units
Journal Issue
Keywords
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