Complexity of geometric optimization by rasterization of Minkowski sums
S. A. Karpukhin
M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
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.
geometric optimization, polytope placement, Minkowski sums, rasterization, numerical methods, computational complexity.
PDF file (235 kB)
S. A. Karpukhin, “Complexity of geometric optimization by rasterization of Minkowski sums”, Num. Meth. Prog., 15:4 (2014), 569–578
Citation in format AMSBIB
\paper Complexity of geometric optimization by rasterization of Minkowski sums
\jour Num. Meth. Prog.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|