I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions

DOI10.1007/978-3-540-77120-3_44MaRDI QIDQ5387782zbMATH OpenOpenAlexFDO

Authors Shripad Thite, Laura Toma, Mark de Berg, Herman Haverkort

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://research.tue.nl/nl/publications/235886bf-c08c-49d2-b0fb-fd62e2422199

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• I/O-efficient dynamic planar point location
• scientific article; zbMATH DE number 1305387
• External memory planar point location with logarithmic updates

Cites work

• An effective way to represent quadtrees
• Approximate range searching
• Cache-oblivious algorithms
• Cache-Oblivious B-Trees
• External-memory algorithms for processing line segments in geographic information systems
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 2086622 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• I/O-efficient dynamic planar point location (extended abstract)
• Introduction to algorithms
• Linear size binary space partitions for uncluttered scenes
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Realistic input models for geometric algorithms

Cited in

(4)

• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• scientific article; zbMATH DE number 1306283 (Why is no real title available?)
• I/O-Efficient Point Location in a Set of Rectangles

This page was built for publication: I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions

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