An optimal time and minimal space algorithm for rectangle intersection problems

DOI10.1007/BF00989481MaRDI QIDQ3318126zbMATH OpenOpenAlexFDO

Authors

Publication date 1984

Published in International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00989481

zbMATH Keywords

analysis of algorithmscomputational geometrydivide-and-conquerdisjoint set union-findrectangle intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Finding Rectangle Intersections by Divide-and-Conquer
• An optimal contour algorithm for iso-oriented rectangles
• Time-and space-optimal contour computation for a set of rectangles
• Hole Problems for Rectangles in the Plane
• Space searching for intersecting objects

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A data structure for dynamic range queries
• A linear-time algorithm for a special case of disjoint set union
• Algorithms for Reporting and Counting Geometric Intersections
• An improved algorithm for the rectangle enclosure problem
• Comments on “algorithms for reporting and counting geometric intersections”
• Decomposable searching problems

Cited in

(7)

• A new algorithm for rectangle enclosure reporting
• The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees
• An optimal contour algorithm for iso-oriented rectangles
• Finding Rectangle Intersections by Divide-and-Conquer
• scientific article; zbMATH DE number 3851099 (Why is no real title available?)
• Optimal algorithms to compute the closure of a set of iso-rectangles
• Space-optimal hidden line elimination for rectangles

This page was built for publication: An optimal time and minimal space algorithm for rectangle intersection problems

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