An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra

DOI10.1137/0221041zbMath0825.68642OpenAlexW2146517658MaRDI QIDQ4018399

Bernard Chazelle

Publication date: 16 January 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221041

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (20)

Extremal polygon containment problems ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ Approximating points by a piecewise linear function ⋮ Bounds on the size of tetrahedralizations ⋮ An Efficient Implementation of Mass Conserving Characteristic-Based Schemes in Two and Three Dimensions ⋮ Unnamed Item ⋮ Conservative interpolation between volume meshes by local Galerkin projection ⋮ Unnamed Item ⋮ Minimum-sum dipolar spanning tree in \(\mathbb R^3\) ⋮ Conservative interpolation on unstructured polyhedral meshes: an extension of the supermesh approach to cell-centered finite-volume variables ⋮ Maximum overlap and minimum convex hull of two convex polyhedra under translations ⋮ Computing hereditary convex structures ⋮ Computing the maximum overlap of two convex polygons under translations ⋮ Solving the diffusion equation on a non-aligned mesh ⋮ A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions ⋮ Generation and Recognition of Digital Planes Using Multi-dimensional Continued Fractions ⋮ Polyhedral GPU Accelerated Shape from Silhouette ⋮ Optimal output-sensitive convex hull algorithms in two and three dimensions ⋮ Conservative remapping and region overlays by intersecting arbitrary polyhedra ⋮ On the planar two-center problem and circular hulls

This page was built for publication: An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra