On the equivalence of some rectangle problems
From MaRDI portal
Publication:1165008
DOI10.1016/0020-0190(82)90068-0zbMath0486.68052OpenAlexW2064303129MaRDI QIDQ1165008
Mark H. Overmars, Herbert Edelsbrunner
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90068-0
computational geometrydominance searchingrectangle containment searchingrectangle enclosure searchingrectangle intersection searching
Related Items (14)
Geometric containment and vector dominance ⋮ Unnamed Item ⋮ The expected size of some graphs in computational geometry ⋮ On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors ⋮ Approximate covering detection among content-based subscriptions using space filling curves ⋮ Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems ⋮ The space-optimal version of a known rectangle enclosure reporting algorithm ⋮ A unified approach to geometric problems using dual cone transformation: ⋮ Adaptive data structures for 2D dominance colored range counting ⋮ On Dominance Reporting in 3D ⋮ A worst-case efficient algorithm for hidden-line elimination† ⋮ Direct dominance of points ⋮ Algorithms for three-dimensional dominance searching in linear space. ⋮ A new algorithm for rectangle enclosure reporting
Cites Work
- Multidimensional divide-and-conquer
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Worst-case optimal insertion and deletion methods for decomposable searching problems
- Priority Search Trees
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Rectilinear line segment intersection, layered segment trees, and dynamization
This page was built for publication: On the equivalence of some rectangle problems
