A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions

DOI10.1007/s00454-016-9785-3zbMath1355.68278OpenAlexW2343046418MaRDI QIDQ728493

Timothy M. Chan

Publication date: 20 December 2016

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5141/

zbMATH Keywords

convex polyhedraintersectionDobkin-Kirkpatrick hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Three-dimensional polytopes (52B10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

An Efficient Implementation of Mass Conserving Characteristic-Based Schemes in Two and Three Dimensions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the planar two-center problem and circular hulls

Cites Work

• Unnamed Item
• Unnamed Item
• Triangulating a simple polygon in linear time
• Applications of random sampling in computational geometry. II
• A linear algorithm for determining the separation of convex polyhedra
• Optimal Search in Planar Subdivisions
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• Convex hulls of finite sets of points in two and three dimensions
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
• A randomized algorithm for triangulating a simple polygon in linear time

This page was built for publication: A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions