Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Num. Meth. Prog., 2014, Volume 15, Issue 4, Pages 569–578 (Mi vmp273)  

Complexity of geometric optimization by rasterization of Minkowski sums

S. A. Karpukhin

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

Full text: PDF file (235 kB)
UDC: 519.6
Received: 21.08.2014

Citation: S. A. Karpukhin, “Complexity of geometric optimization by rasterization of Minkowski sums”, Num. Meth. Prog., 15:4 (2014), 569–578

Citation in format AMSBIB
\Bibitem{Kar14}
\by S.~A.~Karpukhin
\paper Complexity of geometric optimization by rasterization of Minkowski sums
\jour Num. Meth. Prog.
\yr 2014
\vol 15
\issue 4
\pages 569--578
\mathnet{http://mi.mathnet.ru/vmp273}


Linking options:
  • http://mi.mathnet.ru/eng/vmp273
  • http://mi.mathnet.ru/eng/vmp/v15/i4/p569

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Numerical methods and programming
    Number of views:
    This page:106
    Full text:52

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022