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

Начнем с прямолинейной плоскости с препятствиями, заданными в виде прямолинейных многоугольников. Пусть даны n точек на плоскости. Задача состоит в том, чтобы найти кратчайшее прямолинейное дерево Штейнера, соединяющее эти точки. Уже известно, что существует полиномиальная схема аппроксимации для построения прямолинейного минимального дерева Штейнера без препятствий, которая может быть построена методом адаптивного разбиения с применением либо портальной, либо m-гильотинной техники разреза. Однако и m-гильотинный разрез, и метод портала не работают приналичии препятствий. Портальная методика неприменима, так как препятствия могут блокировать движение линии, пересекающей разрез в портале. Провести m-гильотинный разрез также не удается, поскольку препятствия могут разрушить сегмент разреза, обеспечивающий связность дерева Штейнера.

Несмотря на вышеизложенные факты, для RSMT с препятствиями все же могут существовать схемы аппроксимации с полиномиальным временем выполнения. Сильное доказательство этого тезиса было получено в работе Мина и др. [11]. Авторы построили полиномиальную по времени схему аппроксимации для задачи с препятствиями при условии, что отношение самого длинного и самого короткого ребер минимального остовного дерева ограничено константой. Эта схема основывается на классическом неадаптивном подходе к разбиению. Все вышесказанное позволяет предположить, что для случая с препятствиями может быть найден новый адаптивный метод.