Math @ Duke

Publications [#235416] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Brodal, GS; Vitter, JS, I/Oefficient dynamic point location in monotone planar subdivisions,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1999),
pp. 1120
(last updated on 2018/03/19)
Abstract: We present an efficient externalmemory 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(logB2 N) I/Os (worstcase) and updates in O(logB2 N) I/Os (amortized). We also propose a new variant of Btrees, called levelbalanced Btrees, which allow insert, delete, merge, and split operations in O((1+b/BlogM/BN/B)logbN) I/Os (amortized), 2≤b≤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 pointlocation data structure, we believe that levelbalanced Btrees are of significant independent interest. They can, for example, be used to dynamically maintain a planar stgraph using O((1+b/BlogM/BN/B) logb N) = O(logb2 N) I/Os (amortized) per update, so that reachability queries can be answered in O(logB N) I/Os (worst case).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

