О сложности геометрической оптимизации методом растеризации сумм Минковского

Авторы

  • С.А. Карпухин

Ключевые слова:

геометрическая оптимизация
размещение многогранников
суммы Минковского
растеризация
численные методы
сложность вычислений

Аннотация

Рассматривается задача поиска наибольшего многогранника заданной формы (шаблона) внутри другого многогранника и численный метод ее решения при фиксированной ориентации шаблона, основанный на растеризации сумм Минковского. Исследуется сложность данного метода в случае задачи с выпуклым шаблоном и единственным решением в трехмерном пространстве. Доказана ограниченность используемой в алгоритме сетки вне зависимости от точности решения. Выведена теоретическая оценка сверху времени работы алгоритма. Полученная оценка проверена на практической реализации метода.

Новые вычислительные технологии

Загрузки

Опубликован

2014-10-10

Выпуск

Том 15 (2014): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

С.А. Карпухин

Московский государственный университет имени М.В. Ломоносова,
механико-математический факультет
Ленинские горы, 119899, Москва
• аспирант

Библиографические ссылки

  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.