Адаптивные разбиения: различия между версиями

Перейти к навигации Перейти к поиску
Строка 40: Строка 40:
Теперь рассмотрим вариант <math>k \ge 2</math>. Предположим, что в исходном прямоугольнике каждое вертикальное ребро имеет длину <math>a</math>, а каждое горизонтальное – длину <math>b</math>. Рассмотрим два случая:
Теперь рассмотрим вариант <math>k \ge 2</math>. Предположим, что в исходном прямоугольнике каждое вертикальное ребро имеет длину <math>a</math>, а каждое горизонтальное – длину <math>b</math>. Рассмотрим два случая:


''Случай 1''. Существует вертикальный сегмент s, длина которого больше или равна <math>0,5 a</math>. Применим гильотинный разрез вдоль этого сегмента s. Тогда остаток P разделится на две части <math>P_1</math> и <math>P_2</math>, которые образуют прямоугольное разбиение двух получившихся маленьких прямоугольников, соответственно. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что guil(P) < guil(P1) + guil(P2) + a ; length(P) = length(P1) + length(P2) + length(s) ; projx(P) = projx(P1) + projx(P2):
''Случай 1''. Существует вертикальный сегмент s, длина которого больше или равна <math>0,5 a</math>. Применим гильотинный разрез вдоль этого сегмента s. Тогда остаток P разделится на две части <math>P_1</math> и <math>P_2</math>, которые образуют прямоугольное разбиение двух получившихся маленьких прямоугольников, соответственно. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что  


Следовательно, guil(P) < 2- length(P) - projx(P):
<math>guil(P) \le guil(P_1) + guil(P_2) + a</math>,


<math>length(P) = length(P_1) + length(P_2) + length(s)</math>,


Случай 2. Не существует вертикального сегмента s, длина которого больше или равна 0:5a. Выберите горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за P1 и P2 обозначают две части, полученные в результате разбиения прямоугольника P. По предположению индукции, guil(Pi) < 2 ■ length(Pi) - projx(Pi) для i = 1;2. Заметим, что guil(P) = guil(P1) + guil(P2) + b ; length(P) > length(P1) + length(P2) ; projx(P) = projx(P1) = projx(P2) = b :
<math>proj_x(P) = proj_x(P_1) + proj_x(P_2)</math>.


Следовательно, guil(P) < 2 ■ length(P) - projx(P) :
Следовательно, <math>guil(P) \le 2 \cdot length(P) - proj_x(P)</math>.




Гонсалес и Чжэн [ ] улучшили эту верхнюю границу до 1,75 и предположили, что коэффициент эффективности в данном случае равен 1,5.
Случай 2. Не существует вертикального сегмента s, длина которого больше или равна <math>0,5 a</math>. Выберем горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за <math>P_1</math> и <math>P_2</math> две части, полученные в результате разбиения прямоугольника P. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что
 
<math>guil(P) = guil(P_1) + guil(P_2) + b</math>,
 
<math>length(P) \ge length(P_1) + length(P_2)</math>,
 
<math>proj_x(P) = proj_x(P_1) = proj_x(P_2) = b</math>.
 
Следовательно, <math>guil(P) \le 2 \cdot length(P) - proj_x(P)</math>.
 
 
Гонсалес и Чжэн [8] улучшили эту верхнюю границу до 1,75 и предположили, что коэффициент эффективности в данном случае равен 1,5.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Адаптивные_разбиения