Efficient binary space partitions for hidden-surface removal and solid modeling

DOI10.1007/BF02187806zbMATH Open0701.68042OpenAlexW1983698126WikidataQ106190047 ScholiaQ106190047MaRDI QIDQ914380FDOQ914380

Authors: Michael S. Paterson, F. Frances Yao 

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131133

Recommendations

• Optimal binary space partitions for orthogonal objects
• scientific article; zbMATH DE number 2079327
• Binary Space Partitions for Fat Rectangles
• A note on binary plane partitions
• Binary Space Partitions of Orthogonal Subdivisions

zbMATH Keywords

recursive partitioninglower boundsupper boundsbinary space partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The power of geometric duality
• A New Approach to Planar Point Location
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Title not available (Why is that?)

Cited In (36)

• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Multi-way space partitioning trees.
• Binary plane partitions for disjoint line segments
• Estimating the efficiency of a uniform-grid two-dimensional hashing algorithm for hidden line and surface removal in computer graphics
• Cuttings for disks and axis-aligned rectangles in three-space
• Partitioning axis-parallel lines in 3D
• On communication protocols that compute almost privately
• Title not available (Why is that?)
• New results on binary space partitions in the plane
• Spanning trees crossing few barriers
• Conflict neutralization on binary space partitioning
• Applications of a new space-partitioning technique
• Binary space partitions for axis-parallel line segments: Size-height tradeoffs.
• An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
• Local polyhedra and geometric graphs
• Erased arrangements of linear and convex decompositions of polyhedra
• Decomposing the complement of the union of cubes and boxes in three dimensions
• Efficient hidden surface removal for objects with small union size
• Linear size binary space partitions for fat objects
• Visibility with a moving point of view
• DIMENSION-INDEPENDENT BSP (2): BOUNDARY-TO-INTERIOR MAPPING
• New results on binary space partitions in the plane (extended abstract)
• Decompositions and boundary coverings of non-convex fat polyhedra
• Approximate range searching using binary space partitions
• Convex polygons made from few lines and convex decompositions of polyhedra
• Orthogonal dissection into few rectangles
• On optimal cuts of hyperrectangles
• Optimal binary space partitions for segments in the plane
• Binary space partitions of orthogonal subdivisions
• On joints in arrangements of lines in space and related problems
• Title not available (Why is that?)
• Eliminating depth cycles among triangles in three dimensions
• Removing depth-order cycles among triangles: an algorithm generating triangular fragments
• PARALLEL SOLID MODELING USING BSP DATAFLOW
• Perfect binary space partitions
• Binary Space Partitions for Fat Rectangles

This page was built for publication: Efficient binary space partitions for hidden-surface removal and solid modeling

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