Застосування у статистиці

Означення. Відрізок, що сполучає дві найбільш віддалені точки множини S, називається діаметром множини S.

Задача. Діаметр множини. На площині задано N точок. Знайти дві найбільш віддалені одна від іншої точки.

Найпростіший розв’язок задачі – перебрати всі відстані між точками та знайти максимальну із них. Такий розв’язок має часову оцінку O(N2).

Задача. Роздільність множин. Дано дві множини дійсних невід’ємних чисел A = {a1, a2, ..., aN} та B = {b1, b2, ..., bN}. Встановити, чи не містять множини А та В однакових елементів.

Теорема. Задача роздільності множин зводиться до задачі діаметр множини.

Доведення. Відобразимо множини А та В на одиничне коло С, при цьому елементи множини А відобразимо в перший квадрант, а елементи множини В – в третій. Відображення відбувається так: ai відображається в точку перетину кола С з прямою y = aix , що знаходиться в першому квадранті, а bi відображається аналогічним чином в третій квадрант. Позначимо через S множину, яка містить 2 * N побудованих точок перетину.

Множина S має діаметр 2 тоді і тільки тоді, коли вона містить дві діаметрально протилежні точки кола С, тобто коли A B.

Теорема. Нехай uv – діаметр множини S. Нехай lu та lv – дві прямі, перпендикулярні відрізку uv, причому lu проходить через точку u, а lv – через точку v. Тоді точки множини S містяться у смузі, яка визначається прямими lu та lv.

Доведення. Припустимо, що відрізок uv горизонтальний, точка u розташована зліва, v – справа. Побудуємо коло С з центром в точці u та радіусом uv. Пряма lv буде дотичною до кола С, оскільки lv перпендикулярна uv за умовою. Коло С лежить повністю зліва від прямої lv. Оскільки v – найбільш віддалена точка від u, то всі точки множини S лежать всередині кола С, а отже зліва від прямої lv. Аналогічно доводиться, що усі точки множини S лежать справа від прямої lu, що і доводить теорему.

Наслідок. Нехай uv – діаметр множини S. Тоді точки u та v належать опуклій оболонці.

Доведення. Відомо, що точка p належить опуклій оболонці, якщо існує пряма, що проходить через p, а всі точки множини S лежать по одну сторону від цієї прямої. Такими прямими будуть lu та lv.

Теорема. Діаметр множини дорвнює діаметру його опуклої оболонки.

В двовимірному випадку опуклою оболонкою множини точок є опуклий многокутник.

Diam (S) = Diam (CH (S))

Задача. Діаметр опуклого многокутника. Дано опуклий многокутник. Знайти його діаметр.

Теорема. Діаметр опуклої фігури дорівнює найбільшій із відстаней між двома паралельними опорними прямими до цій фігури.

Не через кожну пару точок можна провести паралельні прямі. Наприклад, жодні дві опорні прямі, які проходять через точки p4 та p6, не є паралельними. Це означає, що відрізок p4p6 не є діаметром.

Означення. Пара точок, через які можна провести паралельні опорні прямі, називається протилежною парою.

Дослідимо, як визначити всі протилежні пари, не перебираючі всі можливі пари точок. Будемо рухатися від точки pi по границі многокутника P проти годинникової стрілки до тих пір, поки не досягнемо вершини qi(R), максимально віддаленої від pi-1pi. Якщо P містить паралельні ребра, то в якості qi(R) виберемо першу вершину із вказаною властивістю. Аналогічно визначається вершина qi(L), що максимально віддалена від pipi+1 та визначається при обході многокутника P за годинниковою стрілкою, починаючи з вершини pi.