Kształt alfa
W geometrii obliczeniowej kształt alfa lub kształt α to rodzina fragmentarycznie liniowych prostych krzywych na płaszczyźnie euklidesowej związanych z kształtem skończonego zbioru punktów. Po raz pierwszy zdefiniowali je Edelsbrunner, Kirkpatrick i Seidel (1983) . Kształt alfa powiązany ze zbiorem punktów jest uogólnieniem koncepcji otoczki wypukłej , tzn. każda otoczka wypukła jest postacią alfa, ale nie każda figura alfa jest wypukłą.
Charakteryzacja
Dla każdej liczby rzeczywistej α zdefiniuj pojęcie uogólnionego dysku o promieniu 1/ α w następujący sposób:
- Jeśli α = 0, jest to zamknięta półpłaszczyzna ;
- Jeżeli α > 0, to jest to krążek zamknięty o promieniu 1/ α ;
- Jeśli α < 0, jest to domknięcie dopełnienia dysku o promieniu −1/ α .
Następnie rysowana jest krawędź kształtu alfa między dwoma elementami skończonego zbioru punktów, ilekroć istnieje uogólniony dysk o promieniu 1/α, który nie zawiera żadnego zbioru punktów i który ma tę właściwość, że dwa punkty leżą na jego granicy.
Jeśli α = 0, to kształtem alfa związanym ze skończonym zbiorem punktów jest jego zwykła wypukła otoczka.
kompleks alfa
Kształty alfa są blisko spokrewnione z kompleksami alfa, podkompleksami triangulacji Delaunaya zbioru punktów.
Każda krawędź lub trójkąt triangulacji Delaunaya może być powiązana z charakterystycznym promieniem, promieniem najmniejszego pustego koła zawierającego krawędź lub trójkąt. Dla każdej liczby rzeczywistej α , zespół α danego zbioru punktów jest złożonym uproszczonym utworzonym przez zbiór krawędzi i trójkątów, których promienie wynoszą co najwyżej 1/ α .
Połączenie krawędzi i trójkątów w kompleksie α tworzy kształt bardzo przypominający kształt α ; różni się jednak tym, że ma krawędzie wielokątne, a nie krawędzie utworzone z łuków okręgów. Dokładniej, Edelsbrunner (1995) wykazał, że te dwa kształty są homotopijnie równoważne . (W tej późniejszej pracy Edelsbrunner użył nazwy „ α ” w odniesieniu do połączenia komórek w kompleksie α , a zamiast tego nazwał powiązany kształt krzywoliniowy ciałem α ).
Przykłady
Technikę tę można zastosować do rekonstrukcji powierzchni Fermiego z elektronicznej funkcji widmowej Blocha oszacowanej na poziomie Fermiego , otrzymanej z funkcji Greena w uogólnionym badaniu problemu ab-initio. Powierzchnia Fermiego jest następnie definiowana jako zbiór odwrotnych punktów przestrzennych w pierwszej strefie Brillouina , gdzie sygnał jest najwyższy. Definicja ma tę zaletę, że obejmuje również przypadki różnych postaci zaburzeń.
Zobacz też
- N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, EP Mucke i C. Varela. „ Kształty alfa: definicja i oprogramowanie ”. w Proc. Intern. Oblicz. Geom. Warsztat oprogramowania 1995 , Minneapolis.
- Edelsbrunner, Herbert (1995), „Gładkie powierzchnie do reprezentacji kształtów w wielu skalach”, Podstawy technologii oprogramowania i informatyki teoretycznej (Bangalore, 1995) , Notatki z wykładów w komputerach. Nauka, tom. 1026, Berlin: Springer, s. 391–412, MR 1458090 .
- Edelsbrunner, Herbert ; Kirkpatrick, David G .; Seidel, Raimund (1983), „O kształcie zbioru punktów na płaszczyźnie”, IEEE Transactions on Information Theory , 29 (4): 551–559, doi : 10.1109 / TIT.1983.1056714 .
Linki zewnętrzne
- Kształty alfa 2D i kształty alfa 3D w CGAL , bibliotece algorytmów geometrii obliczeniowej
- Alpha Complex w bibliotece GUDHI.
- Opis i implementacja przez Duke University
- Wszystko, co zawsze chciałeś wiedzieć o kształtach alfa, ale bałeś się zapytać — z ilustracjami i interaktywną demonstracją
- Implementacja kształtu alfa 3D do rekonstrukcji zbiorów 3D z chmury punktów w R
- Omówienie szczegółów implementacji kształtów alfa - wykład przedstawiający formalne i intuicyjne aspekty implementacji kształtów alfa
- Alpha Hulls, Shapes, and Weighted things - slajdy z wykładów Roberta Plessa na Uniwersytecie Waszyngtońskim w St. Louis