Реферат: Разбиения выпуклого многоугольника

Замечание: их существует (n-3).

Определение 2 :Дополнительными диагоналями выпуклого n-угольника называются диагонали, которые в данном разбиении пересекают главные диагонали.

Замечание: их существует менее (n-3).

I.Определение k:

????? ???????? ?? ????????? n-?????????

следующим образом: соединяем диагоналями через одну вершину данного n-угольника, причем выделением считается получение последующего a-угольника из предыдущего, используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (r = 4 или r = 3 (r – остаточный коэффициент)). Назовем каждое такое выделение циклом и введем величину, которая будет “считать” их (d). Для каждого d существует 2^d+1 многоугольников, первый многоугольник для данного d ,будет (2^d+1 +1)-угольником. Для первой половины (для данного d) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (3×2^d )-угольником. Окончательно получаем: r = 3, если nÎ[2^d+1 +1; 3×2^d ], в противном случае r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через d циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой k.

Итак, за 1 цикл 2 пересечения, за 2 цикла – 4, за 3 – 6, очевидна арифметическая прогрессия с разностью 2, a1=2 и количество членов равным d; значит k=2+2(d-1)=2d – только в том случае, если конечной фигурой окажется треугольник. В противном случае k=2d+1, так как четырехугольник имеет собственную диагональ.

Рассчитаем d: т.к.: d=1, n [2² +1; 2³ ]

d=2, n [2³ +1; 2⁴ ]

d=3, n [2⁴ +1; 2⁵ ]

…

Зависимость d от n- логарифмическая по основанию 2; становится очевидным равенство: d=[log₂ (n-1)]-1. Выразим k через n:

k=2([log₂ (n-1)]-1), если nÎ[2^[log2(n-1)] +1; 3×2^{[log2(n-1)]-1} ]

или

k=2([log₂ (n-1)]-1)+1= 2[log₂ (n-1)]-1, если nÏ[2^[log2(n-1)] +1; 3×2^{[log2(n-1)]-1} ]

Так как k – максимум пересечений, то уместны неравенства:

k≤2([log₂ (n-1)]-1), если n Î [2^[log2(n-1)] +1; 3 × 2^{[log2(n-1)]-1} ]

или (*)

k≤2[log₂ (n-1)]-1, если n Ï [2^[log2(n-1)] +1; 3 × 2^{[log2(n-1)]-1} ]

II . Найдем число дополнительных диагоналей ( m), которые пересекают главные не более k раз.

Выделим в данном выпуклом n-угольнике (k+3)-угольник (k+3)-угольник (если это возможно), зн.

уже ‘использовано’ (n+3)-2=k+1 всех

отбросили существующих треугольников

1 треугольник n-угольника (всего их (n-2)),потом добавили другой ‘отбросим’ крайний треугольник и реугольник и ‘добавим’ к получившейся фигуре еще опять получили один, имеющий общую с ней сторону, (k+3)-угольник ‘не использованный’ треугольник, тогда останется (k+2) не использованных треугольника, и так далее до тех пор, пока не ‘используем’ все (n-2)треугольника. Очевидна арифметическая прогрессия с разностью 1, a_m =n-2 и c количеством членов равным m. Получим:n-2=k+1+(m-1)<=>n-2=k+m<=>m=n-k-2-m=n-(k+2)Значит, в n-угольник можно вписать (k+3)угольник (n-(k+2))раз, то есть существуют такие (n-(k+2)) дополнительные диагонали, которые пересекут k главных диагоналей.

Окончательно получаем: P^k _n =( n- (k+2))А _{n ,} где(*).

Список литературы

Скращук Дмитрий (г. Кобрин). Разбиения выпуклого многоугольника