A fast algorithm for polygon containment by translation. (English) Zbl 0571.68029

Fortune, S. J.

Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 189-198 (1985).

[For the entire collection see Zbl 0563.00018.]
The polygon containment problem is the problem of deciding whether one polygon, C, can be translated to fit within another polygon N. We present an algorithm that runs in time O(cn log cn) to solve this problem, in the case that the polygon C is convex. Here c is the number of bounding edges of C, and n is the number of bounding edges of N. The algorithm actually computes the feasible region, that is, a description of the set of all placements of C inside N. The algorithm is close to optimal in that the feasible region may have O(cn) vertices.

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

convex polygon; feasible region

Citations:

Zbl 0563.00018