Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235416] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Arge, L; Brodal, GS; Vitter, JS, I/O-efficient dynamic point location in monotone planar subdivisions, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999), pp. 11-20
    (last updated on 2017/12/16)

    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(logB2 N) I/Os (worst-case) and updates in O(logB2 N) I/Os (amortized). We also propose a new variant of B-trees, called level-balanced B-trees, 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 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+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 27708-0320