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

В работе [9] упоминается несколько возможных приложений данной задачи: управление процессами (сокращение запасов), системы автоматического проектирования топологии интегральных схем (определение каналов), архитектура (устройство внутренних перегородок между кабинетами). Естественной целью для этих задач является разбиение ''с минимальной длиной ребра'', поскольку количество отходов (например, опилок) или затрат (например, на перегородки в офисе) пропорционально сумме длин проведенных ребер. При проектировании СБИС этот критерий используется в системе MIT Placement and Interconnect (PI) для разделения области маршрутизации на каналы, что позволяет получить большие «естественно выглядящие» каналы с минимальным взаимодействием между ними.

Авторы показали, что хотя MELRP в общем случае является недетерминированной задачей с полиномиальным временем выполнения (NP), в случае без отверстий она может быть решена за время <math>O(n^4)</math>, где ''n'' – число вершин входного прямолинейного многоугольника. Полиномиальный алгоритм, по существу, реализует подход динамического программирования, основанный на том, что всегда существует оптимальное решение, удовлетворяющее следующему свойству: каждая линия разреза проходит через вершину входного многоугольника или отверстия (то есть каждый максимальный сегмент разреза инцидентен вершине входного многоугольника или отверстиям).

Наивная идея построения алгоритма аппроксимации для общего случая заключается в использовании леса, соединяющего все отверстия с границей, и последующем решении полученной задачи без отверстий за время <math>O(n^4)</math>. На основе этой идеи Лингас [10] предложил первую аппроксимацию с константными границами, коэффициент эффективности которой равен 41.