Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
From MaRDI portal
Publication:1741853
DOI10.1007/s00453-018-0518-2zbMath1421.68029OpenAlexW2893367356MaRDI QIDQ1741853
Cheng Sheng, Yufei Tao, Xiaocheng Hu
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards optimal two-dimensional indexing for constraint databases
- External-memory algorithms for processing line segments in geographic information systems
- \(\epsilon\)-nets and simplex range queries
- I/O-efficient dynamic planar point location
- Time-space trade-offs for predecessor search
- I/O-Efficient Planar Separators
- On Approximating the Depth and Related Problems
- Decomposable searching problems I. Static-to-dynamic transformation
- New Results on Dynamic Planar Point Location
- Dynamic Point Location in General Subdivisions
- I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
- I/O-efficient point location using persistent B-trees
- Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
- On approximate range counting and depth
- External memory planar point location with logarithmic updates
This page was built for publication: Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os