Intersection removal for simple polygons

Abstract

Given two intersecting simple polygons A and B and a direction, θ, we have to find the minimum distance by which B should be translated along direction θ so that A and B no longer intersect. We present two algorithms for this problem for the case that A and B are in 2 dimensions and one algorithm for the case that they are in 3 dimensions. The 2 dimensional algorithms run in O(N ⁴) and O(N ³ log N) time respectively where N is the total number of vertices in both the polygons while the 3 dimensional algorithm runs in O(N ⁴) time.

Keywords:

• Computational geometry
• simple polygons
• intensity of collision

C.R.Categories:

• F2.2[Analysis of Algorithms and Problem Complexity]
• I.3.5[Computational Geometry and Object Modeling]