I/O-efficient map overlay and point location in low-density subdivisions

M. Berg, de, H.J. Haverkort, S. Thite, L. Toma

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Citaten (Scopus)
1 Downloads (Pure)


We present improved and simplified -efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a low-density subdivision with n edges in i/o’s into a compressed linear quadtree such that one can: • compute the overlay of two preprocessed subdivisions in i/o’s, where n is the total number of edges in the two subdivisions, • answer a single point location query in O(log B n) i/o’s and k batched point location queries in i/o’s. For the special case where the subdivision is a fat triangulation, we show how to obtain the same bounds with an ordinary (uncompressed) quadtree, and we show how to make the structure fully dynamic using O(log B n) i/o’s per update. Our algorithms and data structures improve on the previous best known bounds for general subdivisions both in the number of i/o’s and storage usage, they are significantly simpler, and several of our algorithms are cache-oblivious.
Originele taal-2Engels
TitelProceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan
RedacteurenT. Takuyama
Plaats van productieBerlin
ISBN van geprinte versie3-540-77118-2
StatusGepubliceerd - 2007
Evenement18th International Symposium on Algorithms and Computation (ISAAC 2007) - Sendai, Japan
Duur: 17 dec 200719 dec 2007
Congresnummer: 18

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres18th International Symposium on Algorithms and Computation (ISAAC 2007)
Verkorte titelISAAC 2007
AnderISAAC 2007, Sendai, Japan

Vingerafdruk Duik in de onderzoeksthema's van 'I/O-efficient map overlay and point location in low-density subdivisions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit