Optimal binary space partitions for orthogonal objects

DOI10.1016/0196-6774(92)90007-YzbMath0767.68096OpenAlexW2062612774MaRDI QIDQ3990617

F. Frances Yao, Michael S. Paterson

Publication date: 28 June 1992

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(92)90007-y

zbMATH Keywords

solid modelingray tracingbinary space partitionorthogonal line segmentsreal-time hidden-surface removal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

New results on binary space partitions in the plane (extended abstract) ⋮ OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ On optimal cuts of hyperrectangles ⋮ New results on binary space partitions in the plane ⋮ Linear size binary space partitions for fat objects ⋮ Unnamed Item ⋮ Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications ⋮ Removing depth-order cycles among triangles: an algorithm generating triangular fragments ⋮ Perfect binary space partitions ⋮ Grid vertex-unfolding orthogonal polyhedra ⋮ Binary plane partitions for disjoint line segments ⋮ Approximate range searching using binary space partitions ⋮ Local polyhedra and geometric graphs ⋮ On communication protocols that compute almost privately ⋮ RELATIONS BETWEEN TWO COMMON TYPES OF RECTANGULAR TILINGS ⋮ An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions ⋮ Binary space partitions for axis-parallel line segments: Size-height tradeoffs. ⋮ On constant factors in comparison-based geometric algorithms and data structures