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/CongresprocedureConferentiebijdrageAcademic

103 Downloads (Pure)


We present improved and simplified i/o-efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a lowdensity subdivision with n edges in O(sort(n)) i/o’s into a compressed linear quadtree such that one can: (i) compute the overlay of two such preprocessed subdivisions in O(scan(n)) i/o’s, where n is the total number of edges in the two subdivisions, (ii) answer a single point location query in O(logB n) i/o’s and k batched point location queries in O(scan(n) + sort(k)) 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(logB 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
TitelCollection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria
RedacteurenO. Aichholzer, T. Hackl
Plaats van productieGraz, Austria
UitgeverijVerlag der Technischen Universität Graz
ISBN van geprinte versie978-3-902465-62-7
StatusGepubliceerd - 2007
Evenementconference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 -
Duur: 19 mrt 200721 mrt 2007


Congresconference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21
AnderEWCG 2007, Graz, Austria

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