Реферат на тему:
Застосування у статистиці
Означення. Відрізок, що сполучає дві найбільш віддалені точки множини
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.
Ланцюг вершин між qi(R) та qi(L) (включаючи ці вершини) дає множину
C(pi), кожна вершина якої утворює з pi протилежну пару. Позначимо через
??зовнішній кут, утворений pi-1pi та pipi+1 (? > ?). Пара вершин (pi,
ps) є протилежачою тоді і тільки тоді, коли існує пряма, яка попадає в
перетин кутів ?s та ?i. Оскільки C(pi) – опуклий ланцюг, то кожна його
вершина має вказану властивість.
Протилежні пари
p ??pN;
q ??NEXT[p];
while ( ПЛОЩА (p, NEXT[p], NEXT[q]) > ПЛОЩА (p, NEXT[p], q)) do
q ??NEXT[q]; /* рухатися по границі P поки не буде досягнута вершина,
максимально віддалена від прямої, що сполучає вершини p та NEXT[p] */
q0 ??q;
while (q ??p0) do
begin
p ??NEXT[p];
друк (p, q);
while ( ПЛОЩА (p, NEXT[p], NEXT[q]) > ПЛОЩА (p, NEXT[p], q)) do
begin
q ??NEXT[q];
if (p, q) ??(q0, p0) then друк (p, q);
end;
if ( ПЛОЩА (p, NEXT[p], NEXT[q]) = ПЛОЩА (p, NEXT[p], q)) then
if (p, q) ??(q0, pN) then друк (p, NEXT[q]); /* обробка паралельних
ребер */
end;
Теорема. Діаметр опуклого многокутника може бути знайдено за лінійний по
кількості його вершин час.
Теорема. Діаметр множини з N точок на площині може бути знайдено за
оптимальний час O(N log N).
Теорема. Діаметр простого многокутника може бути знайдено за лінійний
час.
Теорема. На множині з N точок на площині може бути не більше N пар
точок, на яких досягається максимальна відстань між точками множини. При
цьому оцінка досягається на правильних N кутниках (N ??3, непарне).
Означення. Глибиною точки p у множині S називається кількість опуклих
оболонок (опуклих шарів), які повинні бути видалені з S раніше, ніж буде
видалена точка p.
Задача. Глибина множини. На площині задано множину S з N точок.
Визначити глибину кожної точки.
Будуємо опуклу оболонку множини S, потім будуємо опуклу оболонку точок,
які не увійшли до першої оболонки і так далі. Це можна зробити
багатократним обходом Джарвіса.
y = 3x
образ точок
множини А
образ точки 3
множини А
образ точок
множини В
3
1
С
p5
p4
p6
p3
p7
p2
p1
qi(R)
qi(L)
pi-1
pi+1
pi
? s
ps
?i
pi
?i
? s
глибина 1
глибина 2
глибина 3
глибина 4
Початкова точка обходу
Нашли опечатку? Выделите и нажмите CTRL+Enter
