Thumbnail
Access Restriction
Subscribed

Author Vahrenhold, Jan ♦ Hinrichs, Klaus H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract We present an algorithm for external memory planar point location that is both effective and easy to implement. The base algorithm is an external memory variant of the bucket method by Edahiro, Kokubo and Asano that is combined with Lee and Yang's batched internal memory algorithm for planar point location. Although our algorithm is not optimal in terms of its worst-case behavior, we show its efficiency for both batched and single-shot queries by experiments with real-world data. The experiments show that the algorithm benefits from the mainly sequential disk access pattern and significantly outperforms the fastest algorithm for internal memory. Due to its simple concept, the algorithm can take advantage of multiple disks and processors in a rather straightforward yet efficient way.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 7
Starting Page 8


Open content in new tab

   Open content in new tab
Source: ACM Digital Library