Approximate range searching using binary space partitions

DOI10.1016/J.COMGEO.2005.08.003zbMATH Open1137.65326OpenAlexW2041492362MaRDI QIDQ2489539FDOQ2489539

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

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

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)

Cites Work

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

Cited In (11)

• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• Title not available (Why is that?)
• Binary plane partitions for disjoint line segments
• Tight lower bounds for halfspace range searching
• Fast algorithms for approximate Fréchet matching queries in geometric trees
• Approximate Range Searching in External Memory
• Quasi-optimal range searching in spaces of finite VC-dimension
• Computing the visibility map of fat objects
• Approximate range searching in external memory
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Approximate Range Searching: The Absolute Model

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)