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

摘要

Chazelle [FOCS'89] 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.