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

Ланцюг вершин між 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.