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:








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

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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 07:39:03 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section