Как найти минимальные ограничивающие прямоугольники для набора линий?

Question

При условии набора из N соединенных линий на двумерной оси, я ищу алгоритм, который определит X минимальных ограничивающих прямоугольников.

Например, предположим, мне дано 10 строк, и я хотел бы связать их не более чем с 3 (потенциально пересекающимися) прямоугольниками. Таким образом, если 8 линий сгруппированы близко друг к другу, они могут использовать 1 прямоугольник, а две другие могут использовать 2-й или, возможно, также 3-й прямоугольник в зависимости от их близости друг к другу.

Спасибо.

Answer 1

Если линии на самом деле являются путем, то, возможно, вы не будете против требования, чтобы каждый прямоугольник покрывал непрерывную часть пути.В этом случае есть динамическая программа, которая запускается за время O (n ² r), где n - количество сегментов, а r - количество прямоугольников.

Вычислить таблицу с помощьюзаписи C (i, j), обозначающие стоимость покрытия сегментов 1,…, i прямоугольниками j.Повторение для i, j> 0,

C (0, 0) = 0
C (i, 0) = ∞
C (i, j) = minнад i '

Есть O (nr) записейкаждый из которых вычисляется за время O (n).Восстановите оптимальную коллекцию прямоугольников в конце, например, сохранив лучшее i для каждой записи.

Я не знаю простого, оптимального алгоритма для общего случая.Поскольку существуют «только» O (n ⁴ ) прямоугольников, каждый из ребер которых содержит конечную точку сегмента, я хотел бы сформулировать эту проблему как пример покрытия обобщенного набора.