Альфа-форма

Опукла оболонка, альфа-форма та мінімальне кістякове дерево двопараметричного набору даних.

Альфа-форма або α-форма в обчислювальній геометрії — це сімейство кусково-лінійних кривих Евклідової площини, пов'язаних зі скінченною множиною точок. Вперше визначення ввели Едельсбруннер, Кіркпатрік та Зейдель у 1983 році. Альфа-форма, що пов'язана з множиною точок, є узагальненням поняття опуклості, тобто кожна опукла оболонка є альфа-формою, але не кожна альфа-форма є опуклою оболонкою.

Інтуїтивно про α-форму можна думати так. Уявити величезну масу морозива, що створює $\mathbb {R} ^{d}$ і містить точки $S$ у вигляді твердих шматочків шоколаду. Використовуючи ложку для морозива сферичної форми ми видобуваємо все можливе морозиво з блоку, без натикання на шоколадні шматки, навіть утворюючи порожнини всередині (наприклад, частини недосяжні ззовні). Якщо після закінчення ми вирівняємо всі округлі грані в трикутники і відрізки ліній, ми отримаємо інтуїтивний опис того, що називається α-формою $S$.

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

Для кожного цілого числа α, визначити поняття узагальненого диску радіуса 1/α наступним чином:

• 1)Якщо α = 0, це замкнена напівплощина;
• 2)Якщо α > 0, це замкнений диск радіуса 1/α;
• 3)Якщо α < 0, це закрите додавання диска радіуса −1/α.

Ребро альфа-форми змальовується між двома членами набору кінцевих точок тоді , коли існує узагальнений диск з радіусом   1 / α , який містить весь набір точок і який має властивість: обидві точки лежать на його межі.

Якщо α =0, то альфа-форма, пов'язана з заданою кінцевою точкою, є опуклою оболонкою.

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

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

Об'єднання ребер трикутників у «α»-комплекс утворює форму, яка дуже нагадує «α»-форму; однак вона відрізняється тим, що має полігональні ребра. Зокрема, Едельсбруннер в 1995 показав, що ці обидві форми — гомотопно еквівалентні. (У цій пізнішій роботі Едельсбруннер використовував назву «α — форма», щоб нагадати про об'єднання частин у «α»-комплекс. Також він називає пов'язану криволінійну форму «α» — тілом.)

Приклади

Поверхня Фермі: реконструкція альфа-форми. Реконструкція спектральної функції Блоха

Цей метод може бути використаний для реконструкції поверхні Фермі з електронно-спектральної функції Блоха, що оцінюється на рівні рівняння Фермі, отриманої під час досліджень Гріна в загальному вивченні проблеми. Поверхня Фермі визначається як сукупність взаємних пропускних точок в першій зоні Бріллюена, де сигнал є найбільшим. Визначення може пояснити також випадки різних форм безпорядку.

Див. також

• Бета-кістяк

Джерела

• N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela. «Alpha shapes: definition and software». In Proc. Internat. Comput. Geom. Software Workshop 1995, Minneapolis.
• Edelsbrunner, Herbert (1995), Smooth surfaces for multi-scale shape representation, Foundations of software technology and theoretical computer science (Bangalore, 1995), Lecture Notes in Comput. Sci., т. 1026, Berlin: Springer, с. 391—412, MR 1458090
• Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), On the shape of a set of points in the plane, IEEE Transactions on Information Theory, 29 (4): 551—559, doi:10.1109/TIT.1983.1056714

Посилання

• 2D Alpha Shapes [Архівовано 11 жовтня 2016 у Wayback Machine.] and 3D Alpha Shapes [Архівовано 13 серпня 2017 у Wayback Machine.] in CGAL the Computational Geometry Algorithms Library
• Alpha Complex [Архівовано 23 листопада 2017 у Wayback Machine.] in the GUDHI library.
• Description and implementation by Duke University
• Everything You Always Wanted to Know About Alpha Shapes But Were Afraid to Ask [Архівовано 1 листопада 2011 у Wayback Machine.] — with illustrations and interactive demonstration
• Implementation of the 3D alpha-shape for the reconstruction of 3D sets from a point cloud in R [Архівовано 17 липня 2017 у Wayback Machine.]
• Description of the implementation details for alpha shapes [Архівовано 8 березня 2011 у Wayback Machine.] — lecture providing a description of the formal and intuitive aspects of alpha shape implementation
• Alpha Hulls, Shapes, and Weighted things — lecture slides by Robert Pless at the Washington University