Geodesic
Complexity of geometric optimization by rasterization of Minkowski sums
Numerical methods and programming, Tome 15 (2014) no. 4, pp. 569-578.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, Minkowski sums, rasterization, numerical methods, computational complexity.
Mots-clés : polytope placement 
@article{VMP_2014_15_4_a2,
     author = {S. A. Karpukhin},
     title = {Complexity of geometric optimization by rasterization of {Minkowski} sums},
     journal = {Numerical methods and programming},
     pages = {569--578},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2014_15_4_a2/}
}
TY  - JOUR
AU  - S. A. Karpukhin
TI  - Complexity of geometric optimization by rasterization of Minkowski sums
JO  - Numerical methods and programming
PY  - 2014
SP  - 569
EP  - 578
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2014_15_4_a2/
LA  - ru
ID  - VMP_2014_15_4_a2
ER  - 
%0 Journal Article
%A S. A. Karpukhin
%T Complexity of geometric optimization by rasterization of Minkowski sums
%J Numerical methods and programming
%D 2014
%P 569-578
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2014_15_4_a2/
%G ru
%F VMP_2014_15_4_a2
S. A. Karpukhin. Complexity of geometric optimization by rasterization of Minkowski sums. Numerical methods and programming, Tome 15 (2014) no. 4, pp. 569-578. http://geodesic.mathdoc.fr/item/VMP_2014_15_4_a2/