MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Agarwal, Pankaj
Arge, Lars
Brodal, Gerth Stølting
Vitter, Jeffrey Scott		dblp
dblp
dblp
dblp
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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Baltimore, USA},
 MONTH = {January},
 ISBN = {0-89871-434-6},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gerth Stølting Brodal		Created
01/23/1999 19:39:03
Revisions
8.
7.
6.
5.
4.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Uwe Brahm
Uwe Brahm		Edit Dates
30.05.2005 15:31:18
30.05.2005 15:31:04
30.05.2005 15:31:02
04/04/2001 07:43:09 PM
04.04.2000 12:06:14