Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

DOI10.1016/J.COMGEO.2009.11.001MaRDI QIDQ2269835zbMATH OpenOpenAlexFDO

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

Publication date 11 March 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2009.11.001

zbMATH Keywords

algorithmsrange searchingpoint locationQuadtreesfat triangulationsI/O-efficient indexeslow-density subdivisionsmap overlay

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
• I/O-efficient dynamic planar point location
• scientific article; zbMATH DE number 1305387
• External memory planar point location with logarithmic updates
• I/O-efficient point location using persistent B-trees

Cites work

• scientific article; zbMATH DE number 2086622 (Why is no real title available?)
• scientific article; zbMATH DE number 2086641 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• An effective way to represent quadtrees
• Approximate Range Searching in External Memory
• Approximate range searching using binary space partitions
• Cache-Oblivious B-Trees
• Cache-Oblivious Red-Blue Line Segment Intersection
• Cache-oblivious algorithms
• Computational geometry. Algorithms and applications.
• External-memory algorithms for processing line segments in geographic information systems
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Foundations of multidimensional and metric data structures.
• I/O-efficient dynamic planar point location
• Introduction to algorithms
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Realistic input models for geometric algorithms

Cited in

(3)

• On the number of face-connected components of Morton-type space-filling curves
• Robust proximity search for balls using sublinear space
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions

This page was built for publication: Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

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