Building an optimal point-location structure in O(sort(n)) I/Os

DOI10.1007/S00453-018-0518-2MaRDI QIDQ1741853zbMATH OpenOpenAlexFDO

Authors Xiaocheng Hu, Cheng Sheng, Yufei Tao

Publication date 7 May 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-018-0518-2

zbMATH Keywords

bulkloadingcomputational geometryexternal memorypoint location queries

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• I/O-efficient dynamic planar point location
• External memory planar point location with logarithmic updates
• External memory planar point location with logarithmic updates
• I/O-Efficient Point Location in a Set of Rectangles
• I/O-efficient point location using persistent B-trees

Cites work

• -nets and simplex range queries
• Decomposable searching problems I. Static-to-dynamic transformation
• Dynamic Point Location in General Subdivisions
• External memory planar point location with logarithmic updates
• External-memory algorithms for processing line segments in geographic information systems
• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• scientific article; zbMATH DE number 1305387 (Why is no real title available?)
• scientific article; zbMATH DE number 2086622 (Why is no real title available?)
• I/O-efficient dynamic planar point location
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
• I/O-Efficient Planar Separators
• I/O-efficient point location using persistent B-trees
• Multiway simple cycle separators and I/O-efficient algorithms for planar graphs
• New Results on Dynamic Planar Point Location
• On approximate range counting and depth
• On Approximating the Depth and Related Problems
• Time-space trade-offs for predecessor search
• Towards optimal two-dimensional indexing for constraint databases

Cited in

(7)

• Lower bounds for sorted geometric queries in the I/O model
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
• I/O-efficient point location using persistent B-trees
• Algorithms – ESA 2004
• External memory planar point location with logarithmic updates
• Partial order multiway search
• Optimal external memory planar point enclosure

This page was built for publication: Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os

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