Разработка рандомизированного алгоритма построения выпуклой оболочки несимплициального роя точек в многомерном пространстве
Аннотация
Головин А. А. РАЗРАБОТКА РАНДОМИЗИРОВАННОГО АЛГОРИТМА ПОСТРОЕНИЯ ВЫПУКЛОЙ ОБОЛОЧКИ НЕСИМПЛИЦИАЛЬНОГО РОЯ ТОЧЕК В МНОГОМЕРНОМ ПРОСТРАНСТВЕ, выпускная квалификационная работа: стр. 37, рис. 10
Ключевые слова: ВЫПУКЛАЯ ОБОЛОЧКА, НЕСИМПЛИЦИАЛЬНЫЙ ПОЛИТОП, НЕОБЩИЙ СЛУЧАЙ, НЕДЕТЕРМИНИРОВАННЫЙ АЛГОРИТМ, МНОГОМЕРНЫЙ ТЕЛЕСНЫЙ УГОЛ.
В работе предложен недетерминированный (рандомизированный) алгоритм построения выпуклой оболочки конечного множества точек в многомерном пространстве. Упор сделан на преодоление проблемы необщности положения точек: несимплициальность граней политопа выпуклой оболочки, наличие точек роя на гипергранях различных размерностей результирующего политопа. Обсуждаются алгоритмы вычисления многомерных телесных углов при вершинах многомерных симплексов. Предложенный алгоритм был реализован на языке С++, а также были реализованы вспомогательные алгоритмы: генерация тестов, визуализация 2D, 3D, 4D геометрии.
Ключевые слова: ВЫПУКЛАЯ ОБОЛОЧКА, НЕСИМПЛИЦИАЛЬНЫЙ ПОЛИТОП, НЕОБЩИЙ СЛУЧАЙ, НЕДЕТЕРМИНИРОВАННЫЙ АЛГОРИТМ, МНОГОМЕРНЫЙ ТЕЛЕСНЫЙ УГОЛ.
В работе предложен недетерминированный (рандомизированный) алгоритм построения выпуклой оболочки конечного множества точек в многомерном пространстве. Упор сделан на преодоление проблемы необщности положения точек: несимплициальность граней политопа выпуклой оболочки, наличие точек роя на гипергранях различных размерностей результирующего политопа. Обсуждаются алгоритмы вычисления многомерных телесных углов при вершинах многомерных симплексов. Предложенный алгоритм был реализован на языке С++, а также были реализованы вспомогательные алгоритмы: генерация тестов, визуализация 2D, 3D, 4D геометрии.