Approximate range searching using binary space partitions

DOI10.1016/J.COMGEO.2005.08.003MaRDI QIDQ2489539zbMATH OpenOpenAlexFDO

Authors Micha Streppel, Mark 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

Approximate range searchingBinary space partitionsGeometric data structuresRealistic input models

Mathematics Subject Classification ID

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

Recommendations

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Approximate range searching
• Linear size binary space partitions for uncluttered scenes
• Approximate range searching in external memory
• Optimal binary space partitions for orthogonal objects

Cites work

• -nets and simplex range queries
• A note on binary plane partitions
• Approximate range searching
• Binary Space Partitions for Fat Rectangles
• Binary Space Partitions for Line Segments with a Limited Number of Directions
• Box-trees and R-trees with near-optimal query time
• Box-trees for collision checking in industrial installations
• Efficient binary space partitions for hidden-surface removal and solid modeling
• Guarding scenes against invasive hypercubes.
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1305419 (Why is no real title available?)
• Linear size binary space partitions for uncluttered scenes
• New results on binary space partitions in the plane (extended abstract)
• Optimal binary space partitions for orthogonal objects
• Realistic input models for geometric algorithms
• Storing line segments in partition trees
• Surface Approximation and Geometric Partitions

Cited in

(11)

• Quasi-optimal range searching in spaces of finite VC-dimension
• 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
• Approximate Range Searching: The Absolute Model
• Tight lower bounds for halfspace range searching
• scientific article; zbMATH DE number 1945834 (Why is no real title available?)
• Approximate Range Searching in External Memory
• Binary plane partitions for disjoint line segments
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Approximate range searching in external memory

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

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