Построение ячейки Вороного в многомерном пространстве

[Dims]

У меня есть многомерное пространство с расстоянием, в котором имеется система реперных точек. Одна из этих точек выделена (выбрана). Мне надо построить "ячейку Вороного" для этой точки. Ячейка Вороного для заданной точки -- это область пространства, все точки которой ближе к заданной точке, чем к остальным реперным.

Насколько я понимаю, ячейка будет представлять собой N-1 мерный многоугольник, где N размерность исходного пространства.

Фактически, мне нужно найти все другие реперные точки, ячейки которых граничат с заданной. Кроме того, необходимо понимать, какая точка определяет ГРАНЬ (то есть, N-1 мерное подмножество), а какая -- граничит в ребре или другой границе меньшей размерности.

Как же поступить?

Назовём выбранную точку точкой O.

Кажется, на первом этапе можно перебирать все имеющиеся точку. Для каждой точки A строить гиперплоскость, перпендикулярную отрезку OA и проходящую через его середину. Это плоскость будет содержать потенциальную гипергрань. Для простоты можно эту плоскость назвать просто "гипергранью". Обозначим середину отрезка OA через m(A), а гипергрань G(A).

Допустим, мы рассматриваем новую очередную точку B и её гипергрань G(B). Если эта гипергрань пересекает отрезок m(A)-O, то она "выталкивает" старую точку A и про неё можно забыть. Наоборот, если гиперлпоскость G(A) пересекает m(B)-O, то отпадает новая гипергрань. В остальных случаях обе гиперграни остаются во множестве найденных.

В конце мы имеем множество гиперграней, описывающих ячейку Вороного.

Так ли это?

А что же делать с соседними ячейками, контачащими с нашей в меньших по размерности границах? Как их найти?

[worm2]

Dims писал(а):

Допустим, мы рассматриваем новую очередную точку B и её гипергрань G(B). Если эта гипергрань пересекает отрезок m(A)-O, то она "выталкивает" старую точку A и про неё можно забыть. Наоборот, если гиперлпоскость G(A) пересекает m(B)-O, то отпадает новая гипергрань. В остальных случаях обе гиперграни остаются во множестве найденных.

Ситуация сложнее, чем Вы описали. Попробуйте сами применить эти рассуждения к случаю N=2, и Вы увидите, что не всегда это верно.
Указанная Вами задача - это "решение" системы линейных неравенств, т.е. определение минимального подмножества неравенств, которые эквивалентны всему множеству. Думаю, копать нужно в сторону задачи линейного программирования.

Dims писал(а):

А что же делать с соседними ячейками, контачащими с нашей в меньших по размерности границах? Как их найти?

Вам эта задача кажется актуальной? В общем случае такие ячейки будут встречаться достаточно редко, например, в двумерном случае это может случиться, если более 2-х серединных перпендикуляров пересекутся в одной точке. Разве только если в расположении точек наблюдается регулярность... Но малая погрешность во входных данных разрушит эту ситуацию. Конечно, вопросы погрешности тут могут встать при решении этой задачи на ЭВМ...

[Dims]

worm2 писал(а):

Ситуация сложнее, чем Вы описали. Попробуйте сами применить эти рассуждения к случаю N=2, и Вы увидите, что не всегда это верно.

Да, Вы правы. Попытался строго обосновать выкидывание грани и понял, что необоснованно предположил, что каждая грань находится строго отцентрировано по оси, соединяющей точки...

Цитата:

В общем случае такие ячейки будут встречаться достаточно редко

А ведь верно...