A new algorithm for the two-polygon containment problem

A new algorithm for the two-polygon containment problem

0.00 Avg rating0 Votes
Article ID: iaor19972536
Country: United Kingdom
Volume: 24
Issue: 3
Start Page Number: 231
End Page Number: 251
Publication Date: Mar 1997
Journal: Computers and Operations Research
Authors: ,
Keywords: geometry
Abstract:

This article addresses the two-polygon containment problem. The problem is to determine if two polygons, denoted P1, and P2, can fit inside a fixed polygon Q without overlap. The case when P1 and P2 are allowed to translate and rotate and all three polygons are convex, is conisdered. After characterizing the solution space, an approach utilizing mathematical programming is introduced. An efficient algorithm is developed and implemented for the special case when sides of P1 and P2 are matching. The problem is solved by viewing it as a parametric programming problem with a nonlinear parameter. As the algorithm proceeds, optimality conditions (primal feasibility, dual feasibility, and complementary slackness) are maintained continuously. The complexity of the algorithm is O(b(p1+p2)q), where p1, p2, and q are the numbers of vertices in the polygons, and b is the number of dual bases encountered (switches in combinations of contact being maintained) as the angle of rotation ranges through 2; radians. The detailed algebraic development, an example, and computational experience are included.

Reviews

Required fields are marked *. Your email address will not be published.