The problem of finding the largest polytope of a given shape (pattern) inside another polytope is considered. A numerical method based on Minkowski sums rasterization for solving the problem in the case of a pattern with fixed orientation is studied. The method's complexity for the case of the problem with a unique solution and a convex pattern is analyzed. It is proved that the grid used in the algorithm is bounded independently of the solution's accuracy. An upper estimate of the algorithm's running time is derived theoretically. This estimate is confirmed practically.

Keywords: geometric optimization, polytope placement, Minkowski sums, rasterization, numerical methods, computational complexity.

• PDF (Full text in Russian, References in English)   (235KB)



• PDF. zip (Full text in Russian, References in English)   (207KB)