PLANE-SWEEP ALGORITHM FOR FINDING THE TOUCH PARTS OF ROTATING SIMPLE POLYGONS

Let P and Q be two nonintersecting simple polygons in the plane. If P moves around a point and collides with Q , the problem of finding the touch parts of them is discussed. By analyzing the monotone edges of the polygons relative to the point, a method of curves sweep is proposed based on the plane sweep technique, and then an algorithm to solve the problem is given, which runs in time O（（m+n ）log（ m+n ）） in the worst case and has lower time complexity compared with the present algorithm. The method is valuable to the theory and practice in the field of computational geometry and computer graphics.