Альфа-форма

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

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

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

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

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

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

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

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

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

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

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

Приклади

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

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

Див. також

Примітки

  1. ↑ Edelsbrunner, Kirkpatrick, Seidel, 1983.
  2. ↑ Edelsbrunner, 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

Посилання

Вікісховище має мультимедійні дані за темою: Альфа-форма