Optimal binary space partitions for orthogonal objects
From MaRDI portal
Publication:3990617
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
solid modelingray tracingbinary space partitionorthogonal line segmentsreal-time hidden-surface removal
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
