Альфа-форма - Alpha shape

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

В вычислительная геометрия, альфа-форма, или же α-форма, - семейство кусочно-линейных простых кривых в Евклидова плоскость связано с формой конечного набора точек. Впервые они были определены Эдельсбруннер, Киркпатрик и Зайдель (1983). Альфа-форма, связанная с набором точек, является обобщением концепции выпуклый корпус, т.е. каждая выпуклая оболочка является альфа-формой, но не каждая альфа-форма является выпуклой оболочкой.

Характеристика

Для каждого настоящий номер α, определим понятие обобщенный круг радиуса 1/α следующее:

Если α = 0, это замкнутая полуплоскость;
Если α > 0, это замкнутый диск радиуса 1 /α;
Если α <0, это замыкание дополнения к диску радиуса −1 /α.

Затем ребро альфа-формы рисуется между двумя элементами конечного набора точек всякий раз, когда существует обобщенный диск радиуса 1 /α не содержащий ни одного набора точек и обладающий тем свойством, что две точки лежат на его границе.

Если α = 0, то альфа-форма, связанная с множеством конечных точек, является его обычной выпуклой оболочкой.

Альфа комплекс

Альфа-формы тесно связаны с альфа-комплексами, подкомплексами Триангуляция Делоне набора точек.

Каждый край или треугольник Триангуляция Делоне может быть связан с характеристическим радиусом, радиусом наименьшего пустого круга, содержащего край или треугольник. Для каждого настоящий номер α, то α-комплексом заданного набора точек является симплициальный комплекс образованный набором ребер и треугольников с радиусами не более 1 /α.

Объединение ребер и треугольников в α-комплекс образует форму, очень напоминающую α-форма; однако он отличается тем, что у него многоугольные края, а не ребра, образованные дугами окружностей. В частности, Эдельсбруннер (1995) показал, что две формы гомотопический эквивалент. (В этой более поздней работе Эдельсбруннер использовал имя "α-фигура "для обозначения объединения ячеек в α-сложный, и вместо этого назвал связанную криволинейную форму α-тело.)

Примеры

Этот метод может быть использован для восстановления Поверхность Ферми от электронной спектральной функции Блоха, вычисленной на Уровень Ферми, как получено из Зеленая функция в обобщенном ab-initio исследовании проблемы. Затем поверхность Ферми определяется как набор точек обратного пространства в пределах первого Зона Бриллюэна, где сигнал самый высокий. Это определение имеет то преимущество, что охватывает также случаи различных форм расстройства.