Complexity of geometric optimization by rasterization of Minkowski sums

Authors

  • S.A. Karpukhin

Keywords:

geometric optimization
polytope placement
Minkowski sums
rasterization
numerical methods
computational complexity

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.

New computational technologies

Downloads

Published

2014-10-10

Issue

Vol. 15 (2014): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biography

S.A. Karpukhin

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics
• PhD Student

References

  1. Roth L. Optimal containment. Munich: Technical Univ. Munich, 2009.
  2. Deits R., Tedrake R. Computing large convex regions of obstacle-free space through semidefinite programming. 2014 (http://groups.csail.mit.edu/robotics-center/public_papers/Deits14.pdf).
  3. Chebrolu U., Kumar P., Mitchell J.S. B. On finding large empty convex bodies in 3D scenes of polygonal models // Proc. Int. Conf. on Computational Sciences and Its Applications (ICCSA 2008). New York: IEEE Press, 2008. 382-393.
  4. Denny M. Solving geometric optimization problems using graphics hardware // Computer Graphics Forum. 2003. 22, N 3. 441-451.
  5. Pustylnik G. Spatial planning with constraints on translational distances between geometric objects // (http:/www.cs.tau.ac.il/ genap/SpatPlan.pdf).
  6. Lozano-Perez T. Spatial planning: a configuration space approach // IEEE Transactions on Computers. 1983. T. C-32, N 2. 108-120.
  7. Agarwal P.K., Amenta N., Aronov B., Sharir M. Largest placements and motion planning of a convex polygon // Proc. 2nd Int. Workshop on Algorithmic Foundations of Robotics (WAFR’96). Toulouse: Lab. for Analysis and Architecture of Systems, 1996. 143-154.
  8. Koltun V., Sharir M. Polyhedral Voronoi diagrams of polyhedra in three dimensions // Discrete and Computational Geometry. 2004. 31, N 1. 83-124.
  9. Karavelas M.I., Tzanaki E. The maximum number of faces of the Minkowski sum of two convex polytopes // Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2012. 11-28.
  10. Fogel E., Halperin D., Weibel C. On the exact maximum complexity of Minkowski sums of polytopes // Discrete and Computational Geometry. 2009. 42, N 4. 654-669.
  11. Kaufman A.E. Voxels as a computational representation of geometry // CD-ROM Proc. ACM SIGGRAPH’94. The Computational Representation of Geometry. New York: ACM Press, 1994.
  12. Fischer I., Gotsman C. Fast approximation of high-order Voronoi diagrams and distance transforms on the GPU // Journal of Graphics, GPU, and Game Tools. 2006. 11, N 4. 39-60.
  13. Agarwal P.K., Krishnan S., Mustafa N.H., Venkatasubramanian S. Streaming geometric optimization using graphics hardware // Lecture Notes in Computer Science. Vol. 2832. Heidelberg: Springer, 2003. 544-555.
  14. Yuan Z., Rong G., Guo X., Wang W. Generalized Voronoi diagram computation on GPU // Proc. 8th Int. Symp. on Voronoi Diagrams in Science and Engineering. New York: IEEE Press, 2011. 75-82.
  15. Li W., McMains S. Voxelized Minkowski sum computation on the GPU with robust culling // Computer-Aided Design. 2011. 43, N 10. 1270-1283.
  16. Sacks E.P., Kyung M.-H., Milenkovic V. Robust Minkowski sum computation on the GPU. Technical Report N 13-001. West Lafayette: Purdue Univ., 2013.
  17. Hoff K.E., Keyser J., Lin M., et al. Fast computation of generalized Voronoi diagrams using graphics hardware // Proc. 26th Annual Conf. on Computer Graphics and Interactive Techniques. New York: ACM Press, 1999. 277-286.
  18. Varadhan G., Manocha D. Accurate Minkowski sum approximation of polyhedral models // Graphical Models. 2006. 68, N 4. 343-355.
  19. Barki H., Denis F., Dupont F. Contributing vertices-based Minkowski sum computation of convex polyhedra // Computer-Aided Design. 2009. 41, N 7. 525-538.
  20. Карпухин С.А. О геометрической оптимизации методом растеризации сумм Минковского // Программная инженерия. 2014. № 6. 19-22.
  21. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. М.: Физматлит, 2004.
  22. Александров А.Д. Выпуклые многогранники. Л.: ГИТТЛ, 1950.
  23. Иванов Д.В., Карпов А.С., Кузьмин Е.П., Лемпицкий В.С., Хропов А.А. Алгоритмические основы растровой машинной графики. М.: БИНОМ, 2007.