Approximate range searching using binary space partitions

DOI10.1016/j.comgeo.2005.08.003zbMath1137.65326OpenAlexW2041492362MaRDI QIDQ2489539

Micha Streppel, Mark T. de Berg

Publication date: 28 April 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://idus.us.es/xmlui/handle/11441/55394

zbMATH Keywords

Binary space partitionsApproximate range searchingGeometric data structuresRealistic input models

Mathematics Subject Classification ID

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

Related Items (6)

Approximate range searching in external memory ⋮ Approximate Range Searching in External Memory ⋮ Binary plane partitions for disjoint line segments ⋮ Computing the visibility map of fat objects ⋮ Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions ⋮ Fast algorithms for approximate Fréchet matching queries in geometric trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Storing line segments in partition trees
• Efficient binary space partitions for hidden-surface removal and solid modeling
• \(\epsilon\)-nets and simplex range queries
• A note on binary plane partitions
• Guarding scenes against invasive hypercubes.
• Linear size binary space partitions for uncluttered scenes
• Approximate range searching
• Box-trees and R-trees with near-optimal query time
• Realistic input models for geometric algorithms
• Optimal binary space partitions for orthogonal objects
• Surface Approximation and Geometric Partitions
• Box-trees for collision checking in industrial installations
• Binary Space Partitions for Line Segments with a Limited Number of Directions
• Binary Space Partitions for Fat Rectangles
• New results on binary space partitions in the plane (extended abstract)

This page was built for publication: Approximate range searching using binary space partitions