Альфа-форма
В вычислительной геометрии альфа -форма , или α-форма , представляет собой семейство кусочно-линейных простых кривых в евклидовой плоскости, связанных с формой конечного набора точек. Впервые они были определены Эдельсбруннером, Киркпатриком и Зейделем (1983) . Альфа-форма, связанная с набором точек, является обобщением концепции выпуклой оболочки , т.е. каждая выпуклая оболочка является альфа-формой, но не каждая альфа-форма является выпуклой оболочкой.
Характеристика
[ редактировать ]Для каждого действительного числа α определим понятие обобщенного диска радиуса 1/ α следующим образом:
- Если α = 0, это замкнутая полуплоскость ;
- Если α > 0, то это замкнутый диск радиуса 1/ α ;
- Если α < 0, это замыкание дополнения к кругу радиуса −1/ α .
Затем край альфа-формы рисуется между двумя членами конечного множества точек всякий раз, когда существует обобщенный диск радиуса 1/ α, который имеет две точки на своей границе и который не содержит ни одной точки из множества точек внутри себя .
Если α = 0, то альфа-форма, связанная с конечным множеством точек, является его обычной выпуклой оболочкой.
Альфа-комплекс
[ редактировать ]Альфа-формы тесно связаны с альфа-комплексами, подкомплексами триангуляции Делоне множества точек.
Каждому ребру или треугольнику триангуляции Делоне может быть сопоставлен характерный радиус - радиус наименьшего пустого круга, содержащего ребро или треугольник. Для каждого вещественного числа α -комплекс α данного набора точек представляет собой симплициальный комплекс, образованный множеством ребер и треугольников, радиусы которых не превосходят 1/ α .
α - комплекс также является подкомплексом комплекса Чеха , но в вычислительном отношении более эффективен, если окружающее пространство имеет размерность 2 или 3. [1] [2]
Объединение ребер и треугольников в α -комплексе образует форму, очень похожую на α -форму; однако он отличается тем, что имеет многоугольные края, а не края, образованные дугами кругов. Более конкретно, Эдельсбруннер (1995) показал, что эти две формы гомотопически эквивалентны . (В этой более поздней работе Эдельсбруннер использовал название « α -форма» для обозначения объединения клеток в α -комплексе и вместо этого назвал соответствующую криволинейную форму α -телом.)
Примеры
[ редактировать ]Этот метод можно использовать для восстановления поверхности Ферми по электронной спектральной функции Блоха, оцененной на уровне Ферми , полученной из функции Грина в обобщенном ab-initio исследовании проблемы. Тогда поверхность Ферми определяется как набор точек обратного пространства внутри первой зоны Бриллюэна , где сигнал самый высокий. Преимущество этого определения состоит в том, что оно охватывает также случаи различных форм беспорядков.
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( сентябрь 2011 г. ) |
См. также
[ редактировать ]Ссылки
[ редактировать ]- Н. Аккираджу, Х. Эдельсбруннер, М. Фаселло, П. Фу, Э. П. Муке и К. Варела. « Альфа-формы: определение и программное обеспечение ». В Proc. Интерн. Вычислить. Геом. Семинар по программному обеспечению, 1995 г. , Миннеаполис.
- Эдельсбруннер, Герберт (1995), «Гладкие поверхности для многомасштабного представления форм», Основы программных технологий и теоретической информатики (Бангалор, 1995) , Конспекты лекций по вычислительной технике. наук, том. 1026, Берлин: Springer, стр. 391–412, MR 1458090 .
- Эдельсбруннер, Герберт ; Киркпатрик, Дэвид Г .; Зайдель, Раймунд (1983), «О форме множества точек на плоскости», IEEE Transactions on Information Theory , 29 (4): 551–559, doi : 10.1109/TIT.1983.1056714 .
Внешние ссылки
[ редактировать ]- 2D-альфа-формы и 3D-альфа-формы в CGAL, библиотеке алгоритмов вычислительной геометрии
- Альфа-комплекс в библиотеке GUDHI.
- Описание и реализация Университета Дьюка
- Все, что вы всегда хотели знать об альфа-формах, но боялись спросить – с иллюстрациями и интерактивной демонстрацией
- Реализация 3D-альфа-формы для реконструкции 3D-наборов из облака точек в R.
- Описание деталей реализации альфа-форм – лекция с описанием формальных и интуитивных аспектов реализации альфа-форм.
- Альфа-корпуса, формы и взвешенные предметы – слайды лекций Роберта Плесса в Вашингтонском университете в Сент-Луисе