Triangulacja Delone

Przykładowa triangulacja.

Na czerwono zaznaczono środki okręgów opisanych, które stanowią wierzchołki diagramu Woronoja.

Triangulacja Delone (w powszechnym użyciu jest pisownia nazwiska Delaunay) to triangulacja T przestrzeni Rⁿ⁺¹ zdefiniowana następująco:

T to podział Rⁿ⁺¹ na (n+1)-sympleksy, takie że:

każde dwa sympleksy z T mają wspólną ścianę lub nie mają części wspólnej wcale
każdy ograniczony zbiór w Rⁿ⁺¹ ma część wspólną jedynie ze skończenie wieloma sympleksami z T
wnętrze kuli opisanej na dowolnym sympleksie z T nie zawiera wierzchołków żadnego sympleksu z T

Triangulacja Delone jest grafem dualnym diagramu Woronoja. Została wymyślona przez rosyjskiego matematyka Borysa Delone w 1934.

[edytuj] Bibliografia

Triangulacja Delaunaya. W: Mark de Berg, Mirosław Kowaluk: Geometria obliczeniowa : algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 221-250. ISBN 978-83-204-3244-2.