de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### I/O-Efficient Dynamic Point Location in Monotone Subdivisions

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44187

Brodal,  Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Agarwal, P., Arge, L., Brodal, G. S., & Vitter, J. S. (1999). I/O-Efficient Dynamic Point Location in Monotone Subdivisions. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-99) (pp. 11-20). New York, USA: ACM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-35D5-E
##### 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(\log_{B}^{2} N)$ I/Os (worst-case) and updates in $O(\log_{B}^{2} N)$ I/Os (amortized). We also propose a new variant of $B$-trees, called {\em level-balanced $B$-trees}, which allow insert, delete, merge, and split operations in $O((1+\frac{b}{B}\log_{M/B} \frac{N}{B})\log_{b} N)$ I/Os (amortized), $2\leq b\leq 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 {\em 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+\frac{b}{B}\log_{M/B} \frac{N}{B})\log_{b} N)=O(\log_{B}^{2} N)$ I/Os (amortized) per update, so that reachability queries can be answered in $O(\log_{B} N)$ I/Os (worst case).