Optimal binary space partitions for orthogonal objects

DOI10.1016/0196-6774(92)90007-YzbMATH Open0767.68096OpenAlexW2062612774MaRDI QIDQ3990617FDOQ3990617

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

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

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)

Cited In (34)

• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Binary Space Partitions of Orthogonal Subdivisions
• Multi-way space partitioning trees.
• Title not available (Why is that?)
• Binary plane partitions for disjoint line segments
• Binary plane partitions for disjoint line segments
• RELATIONS BETWEEN TWO COMMON TYPES OF RECTANGULAR TILINGS
• Cuttings for disks and axis-aligned rectangles in three-space
• Binary space partitions: recent developments
• Optimal binary space partitions in the plane
• Efficient binary space partitions for hidden-surface removal and solid modeling
• Partitioning axis-parallel lines in 3D
• On communication protocols that compute almost privately
• Title not available (Why is that?)
• 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
• Linear size binary space partitions for fat objects
• An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions
• New results on binary space partitions in the plane (extended abstract)
• Linear size binary space partitions for uncluttered scenes
• Binary space partition for orthogonal fat rectangles
• Approximate range searching using binary space partitions
• 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
• Binary Space Partitions for Fat Rectangles

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)