Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Editor(s):
 BibTeX cite key*: Agarwal99

 Title, Booktitle
 Title*: I/O-Efficient Dynamic Point Location in Monotone Subdivisions Booktitle*: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-99)

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Baltimore, USA Language: English Event Date* (no longer used): January, 17 - January 19 Organization: ACM-SIAM Event Start Date: 17 January 1999 Event End Date: 19 January 1999

 Publisher
 Name*: ACM URL: Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: January Pages: 11-20 Year*: 1999 VG Wort Pages: ISBN/ISSN: 0-89871-434-6 Sequence Number: DOI:

 (LaTeX) 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). Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:

@INPROCEEDINGS{Agarwal99,
AUTHOR = {Agarwal, Pankaj and Arge, Lars and Brodal, Gerth Stølting and Vitter, Jeffrey Scott},
TITLE = {I/O-Efficient Dynamic Point Location in Monotone Subdivisions},
BOOKTITLE = {Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-99)},
PUBLISHER = {ACM},
YEAR = {1999},
ORGANIZATION = {ACM-SIAM},
PAGES = {11--20},