OPTIMAL ALGORITHM FOR DECIDING COLLISION OF POLYGONS IN RIGID BODY DISPLACEMENT ALONG CURVES
Qin Zhongping, Huanguo Zhang · Chinese Journal of Computers · 1997
Let σ be a regular curve, P and Q two simple polygons. This paper discusses the problem of deciding whether P collides with Q when P takes rigid body displacement along curve σ, and gives an O(mn) time decision algorithm, where m and n are the numbers of venices of P and Q, respectively. The algorithm is optimal in the worst case.