Застосування у статистиці, Детальна інформація
Застосування у статистиці
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
друк (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
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021