A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

作者：Chan Timothy M^*

来源：Discrete & Computational Geometry, 2016, 56(4): 860-865.

DOI：10.1007/s00454-016-9785-3

• Convex polyhedra
• Intersection
• Dobkin-Kirkpatrick hierarchy

Chazelle [SIAM J Comput 21(4):671-696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

• 出版日期2016-12