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

DOI10.1016/J.COMGEO.2009.11.001zbMATH Open1187.65021OpenAlexW2082590257MaRDI QIDQ2269835FDOQ2269835

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

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

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)

Cites Work

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

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)