On the equivalence of some rectangle problems

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

zbMATH Keywords

computational geometrydominance searchingrectangle containment searchingrectangle enclosure searchingrectangle intersection searching

Mathematics Subject Classification ID

Searching and sorting (68P10)

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