МНОГОМЕРНЫЙ АЛГОРИТМ ОВЫПУКЛЕНИЯ РОЯ ТОЧЕК, НАХОДЯЩИХСЯ В НЕОБЩЕМ ПОЛОЖЕНИИ

Аннотация

Целью работы является разработка и реализация алгоритма построения выпуклой оболочки многомерного роя точек в случае их необщего положения. Под необщим положением точек подразумевается ситуация, когда в (d-1)-мерной гиперплоскости пространства R^d лежит больше, чем d точек. Процедура реализует метод заворачивания подарка. Особенностью предлагаемой версии алгоритма является то, что после нахождения плоскости очередной гиперграни проводится построение выпуклой оболочки подроя точек, попавших в аффинное пространство этой гиперплоскости. Этот рекурсивный переход в пространство меньшей размерности проводится тогда, когда точек слишком много, чтобы образовать симплициальную гипергрань. В процессе построения гиперграни накапливается информация о её гиперрёбрах, необходимая для перехода к соседним граням. В целом, алгоритм заворачивания подарка реализует поиск в ширину в графе, в котором вершины соответствуют граням конструируемой выпуклой оболочки, а рёбра соединят вершины, соответствующие граням, имеющим общее гиперребро. Предложенный алгоритм реализован в виде программы на языке C# для среды исполнения .