4511
правок
Адаптивные разбиения: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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>. Заметим, что | ''Случай 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>. Заметим, что | ||
<math>guil(P) \le guil(P_1) + guil(P_2) + a</math>, | |||
<math>length(P) = length(P_1) + length(P_2) + length(s)</math>, | |||
<math>proj_x(P) = proj_x(P_1) + proj_x(P_2)</math>. | |||
Следовательно, guil(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. | |||
== Применение == | == Применение == | ||