Delonay üçbucaqlanması

Təyyarədə verilmiş nöqtələr çoxluğunun triangulyasiyası aşağıdakı şərtləri ödəyən deqenerasiya olunmamış üçbucaqlar çoxluğudur:

1. Üçbucaqların təpə nöqtələri yalnız verilmiş nöqtələrdən ibarətdir. İlkin çoxluğun hər bir nöqtəsi ən azı bir üçbucağın təpə nöqtəsidir.

2. İki fərqli üçbucaq ya heç bir nöqtəni paylaşmır, ya ortaq bir təpəsi, ya da ortaq bir tərəfi var (amma onların kəsişmə sahəsi həmişə $0$-a bərabərdir).

3. İlkin nöqtələr çoxluğunun çevrilmiş örtüyü (çevik örtüyü) daxilində yerləşən istənilən nöqtə ən azı bir üçbucağa daxildir (əgər ümumi təpə nöqtəsi və ya ortaq tərəfdə yerləşirsə, bir neçə üçbucağa da daxil ola bilər). (Nöqtələr çoxluğunun çevik örtüyü həmin nöqtələrin hamısını əhatə edən ən kiçik çevik çoxbucaqdır).

Bir triangulyasiya aşağıdakı əlavə şərti də ödəyirsə, Delaunay triangulyasiyası adlanır:

• Triangulyasiyadakı istənilən üçbucağına çevrilən çevrə daxilində heç bir başlanğıc nöqtəsi yoxdur (nöqtələr çevrədə yerləşə bilər; xüsusən, aydındır ki, üçbucağın təpə nöqtələri çevrədədir).

Verilmiş nöqtələr çoxluğu üçün onun Delaunay triangulyasiyalarının sayını müəyyən edin (iki triangulyasiya fərqli sayılır, əgər ən azı bir üçbucaqda fərqlənirlərsə).