Застосування у статистиці, Детальна інформація

p \xF0AC\xF020NEXT[p];

друк (p, q);

while ( ПЛОЩА (p, NEXT[p], NEXT[q]) > ПЛОЩА (p, NEXT[p], q)) do

begin

q \xF0AC\xF020NEXT[q];

if (p, q) \xF0B9\xF020(q0, p0) then друк (p, q);

end;

if ( ПЛОЩА (p, NEXT[p], NEXT[q]) = ПЛОЩА (p, NEXT[p], q)) then

if (p, q) \xF0B9\xF020(q0, pN) then друк (p, NEXT[q]); /* обробка паралельних ребер */

end;

Теорема. Діаметр опуклого многокутника може бути знайдено за лінійний по кількості його вершин час.

Теорема. Діаметр множини з N точок на площині може бути знайдено за оптимальний час O(N log N).

Теорема. Діаметр простого многокутника може бути знайдено за лінійний час.

Теорема. На множині з N точок на площині може бути не більше N пар точок, на яких досягається максимальна відстань між точками множини. При цьому оцінка досягається на правильних N кутниках (N \xF0B3\xF0203, непарне).

Означення. Глибиною точки p у множині S називається кількість опуклих оболонок (опуклих шарів), які повинні бути видалені з S раніше, ніж буде видалена точка p.

Задача. Глибина множини. На площині задано множину S з N точок. Визначити глибину кожної точки.

Будуємо опуклу оболонку множини S, потім будуємо опуклу оболонку точок, які не увійшли до першої оболонки і так далі. Це можна зробити багатократним обходом Джарвіса.

y = 3x

образ точок

множини А

образ точки 3

множини А

образ точок

множини В

3

1

С

p5

p4

p6