Optimal binary space partitions for orthogonal objects

DOI10.1016/0196-6774(92)90007-YMaRDI QIDQ3990617zbMATH OpenOpenAlexFDO

Authors Michael S. Paterson, F. Frances Yao

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

ray tracingbinary space partitionsolid modelingorthogonal 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)

Recommendations

• Optimal binary space partitions in the plane
• Optimal binary space partitions for segments in the plane
• Binary space partition for orthogonal fat rectangles
• Binary Space Partitions of Orthogonal Subdivisions
• Binary space partitions of orthogonal subdivisions
• Optimal separable partitioning in the plane
• Binary Space Partitions for Axis-Aligned Fat Rectangles
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• scientific article; zbMATH DE number 2119698

Cited in

(34)

• Binary Space Partitions for Fat Rectangles
• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Binary Space Partitions of Orthogonal Subdivisions
• Multi-way space partitioning trees.
• scientific article; zbMATH DE number 2079327 (Why is no real title available?)
• Binary plane partitions for disjoint line segments
• RELATIONS BETWEEN TWO COMMON TYPES OF RECTANGULAR TILINGS
• Binary plane partitions for disjoint line segments
• Cuttings for disks and axis-aligned rectangles in three-space
• Efficient binary space partitions for hidden-surface removal and solid modeling
• Binary space partitions: recent developments
• Optimal binary space partitions in the plane
• Partitioning axis-parallel lines in 3D
• On communication protocols that compute almost privately
• scientific article; zbMATH DE number 1911009 (Why is no real title available?)
• On constant factors in comparison-based geometric algorithms and data structures
• New results on binary space partitions in the plane
• Conflict neutralization on binary space partitioning
• Binary space partitions for axis-parallel line segments: Size-height tradeoffs.
• Grid vertex-unfolding orthogonal polyhedra
• Local polyhedra and geometric graphs
• Decomposing the complement of the union of cubes and boxes in three dimensions
• An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions
• Linear size binary space partitions for fat objects
• Linear size binary space partitions for uncluttered scenes
• New results on binary space partitions in the plane (extended abstract)
• Approximate range searching using binary space partitions
• Binary space partition for orthogonal fat rectangles
• Exact size of binary space partitionings and improved rectangle tiling algorithms
• On optimal cuts of hyperrectangles
• Optimal binary space partitions for segments in the plane
• Binary space partitions of orthogonal subdivisions
• Removing depth-order cycles among triangles: an algorithm generating triangular fragments
• Perfect binary space partitions

This page was built for publication: Optimal binary space partitions for orthogonal objects

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