Optimal external memory planar point enclosure

DOI10.1007/S00453-007-9126-2MaRDI QIDQ834582zbMATH OpenOpenAlexFDO

Authors Lars Arge, Vasilis Samoladas, Ke Yi

Publication date 27 August 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9126-2

zbMATH Keywords

data structuresexternal memory algorithmspoint enclosure

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Recommendations

• Algorithms – ESA 2004
• I/O-Efficient Point Location in a Set of Rectangles
• External memory planar point location with logarithmic updates
• I/O-efficient dynamic planar point location
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os

Cites work

• scientific article; zbMATH DE number 1670656 (Why is no real title available?)
• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 910894 (Why is no real title available?)
• A new approach to rectangle intersections part I
• Box-trees and R-trees with near-optimal query time
• Filtering Search: A New Approach to Query-Answering
• Fractional cascading. I: A data structuring technique
• How to find a battleship
• I/O-efficient point location using persistent B-trees
• Lower bounds for orthogonal range searching: I. The reporting case
• Making data structures persistent
• Multidimensional divide-and-conquer
• On a model of indexability and its bounds for range queries
• Optimal External Memory Interval Management
• The priority R-tree: a practically efficient and worst-case optimal R-tree

Cited in

(4)

• scientific article; zbMATH DE number 7561469 (Why is no real title available?)
• Algorithms – ESA 2004
• Planar point location for large data sets
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems

This page was built for publication: Optimal external memory planar point enclosure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834582)