Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Optimal External-Memory Planar Point Enclosure

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Lars Arge
  • Vasilis Samoladas, Department of Electronics and Computer Engineering, Technical University of Crete, Chania, Greece
  • Ke Yi, Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
  • Department of Computer Science
In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log  B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B 1−ε ) disk blocks are needed for some constant ε>0. With linear space, the best obtainable query bound is O(log 2 N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds.
Original languageEnglish
JournalAlgorithmica
Volume54
Issue3
Pages (from-to)337-352
Number of pages16
ISSN0178-4617
DOIs
Publication statusPublished - 20 Nov 2007

    Research areas

  • External memory algorithms, Point enclosure, Data structures

See relations at Aarhus University Citationformats

ID: 6215925