Вороной полюс

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

Определение

Example
Here x is the positive pole of V_p and y its negative. As the cell corresponding to q is unbounded, only the negative pole z exists.

Позволять $V$ быть диаграммой Вороного для набора сайтов $P$, и пусть $V_{p}$ быть ячейкой Вороного $V$ соответствующий сайту $p\in P$. Если $V_{p}$ ограничена, то ее положительный полюс является вершиной границы $V_{p}$ который имеет максимальное расстояние до точки $p$. Если ячейка неограничена, то положительный полюс не определен.

Кроме того, пусть ${\bar {u}}$ быть вектором из $p$ к положительному полюсу, или, если ячейка неограничена, пусть ${\bar {u}}$ — вектор в среднем направлении всех неограниченных ребер Вороного ячейки. Отрицательный полюс тогда является вершиной Вороного. $v$ в $V_{p}$ с наибольшим расстоянием до $p$ такой, что вектор ${\bar {u}}$ и вектор из $p$ к $v$ сделать угол больше, чем ${\tfrac {\pi }{2}}$.

История и применение

Полюса были представлены в 1998 году в двух статьях Нины Аменты , Маршалла Берна и Манолиса Келлиса по проблеме реконструкции поверхности . Как они показали, любую гладкую поверхность , отбираемую с плотностью выборки, обратно пропорциональной ее кривизне, можно точно реконструировать, построив триангуляцию Делоне из объединенного набора точек выборки и их полюсов, а затем удалив определенные треугольники, почти параллельные поверхности. отрезки линий между парами близлежащих полюсов.