Тріангуляція Делоне

Тріангуляцією множини точок на площині називається набір невироджених трикутників, які задовольняють такі умови:

1. Вершини трикутників — лише точки з початкової множини. Кожна точка початкової множини є вершиною щонайменше одного трикутника.

2. Два різні трикутники або не мають спільних точок, або мають спільну вершину, або мають спільну сторону (але площа їх перетину завжди дорівнює $0$).

3. Будь-яка точка, розташована всередині опуклої оболонки початкової множини точок, належить щонайменше одному трикутнику (вона може належати декільком трикутникам, якщо це спільна вершина або лежить на спільній стороні). (Опукла оболонка множини точок — це найменший опуклий багатокутник, що містить усі ці точки).

Тріангуляція називається тріангуляцією Делоне, якщо додатково виконується така умова:

• Внутрішня область описаного кола навколо будь-якого трикутника тріангуляції не містить жодної з початкових точок (точки можуть лежати на колі; зокрема, очевидно, вершини трикутника лежать на колі).

Для заданої множини точок визначте кількість її тріангуляцій Делоне (дві тріангуляції вважаються різними, якщо вони відрізняються хоча б одним трикутником).