Delaunayova triangulace - dokončení

Pravidla pro volbu bodů p_0, p_1 a p_2.

Konvexní obal v R^3

Konvexní obal n bodů v prostoru má nejvýše 3n-6 hran a 2n-4 stěn.  Náhodnostní přírustkový algoritmus. Najdeme 4 body tvořící čtyrstěn. Další náhodně seřadíme a postupně přidáváme.  Z konvexního obalu pro r-1 bodu vytvorime konvexní obal pro r bodů. Popis konvexního obalu pomocí dvojitě souvosleho seznamu. Tvorba nových stěn. Technická realizace pomocí tzv konfliktních seznamů a bipartitního grafu. Algoritmus. Očekávaná paměťová náročnost O(n), očekávaný čas O(n log n).