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

algorithmsfat triangulationsI/O-efficient indexeslow-density subdivisionsmap overlaypoint locationQuadtreesrange searching

Mathematics Subject Classification ID

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

Review text

The authors present improved and simplified algorithms for map overlay, point location and range searching in an external memory for fat triangulations and low-density subdivisions. These are based on a quadtree which is defined to ensure that each leaf intersects only a constant number of edges of the subdivision. The authors also compare their results with the corresponding results given by \textit{L. Arge, D. E. Vengroff} and \textit{J. S. Vitter} [Algorithmica 47, 1--25 (2007; Zbl 1107.68118); and \textit{A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer} and \textit{E. A. Ramos} [Comput. Geom. Theory Appl. 11, 305--337 (2001; Zbl 1074.68669)].

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

• An effective way to represent quadtrees
• Approximate Range Searching in External Memory
• Approximate range searching using binary space partitions
• Cache-oblivious algorithms
• Cache-Oblivious B-Trees
• Cache-Oblivious Red-Blue Line Segment Intersection
• Computational geometry. Algorithms and applications.
• External-memory algorithms for processing line segments in geographic information systems
• Foundations of multidimensional and metric data structures.
• 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 2086641 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• 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)

• Robust proximity search for balls using sublinear space
• On the number of face-connected components of Morton-type space-filling curves
• 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)