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

В 1996 году Арора [ ] и Митчелл и др. [12, 13, 14] обнаружили, что для того, чтобы иметь вычислимое за полиномиальное время оптимальное решение для такой последовательности разрезов, разрез не обязательно должен быть полностью гильотинным. Конечно, количество связей, остающихся после неполного гильотинного разреза, должно быть ограничено. Митчелл и коллеги разработали технику m-гильотинного разбиения, тогда как Арора применил технологию «портала». Исследователи также обнаружили, что их методы могут быть использованы не только для MELRP, но и для многих задач геометрической оптимизации [1, 2, 3, 12, 13, 14, 15].