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

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

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

Спасибо.


algorithm geometry graphics 2d
person glutz    schedule 14.12.2011    source источник
comment
Извините, я не понял, что вы хотите минимизировать: количество прямоугольников? совокупная площадь прямоугольников? Что-то другое?   -  person Miquel    schedule 14.12.2011
comment
агрегированная площадь. Извините за путаницу.   -  person glutz    schedule 14.12.2011
comment
Спасибо за дополнительную информацию. Теперь я думаю об этом, однако, вам нужно больше ограничений, или вы можете просто сделать супер крошечный прямоугольник вокруг каждой точки (столько прямоугольников, сколько точек), и все будет готово.   -  person Miquel    schedule 14.12.2011
comment
В ПОРЯДКЕ. Я сделал ошибку здесь. На самом деле я хочу связать линии, соединяющие точки, а не сами точки. И в большинстве случаев мне никогда не нужно больше 4 прямоугольников, поэтому простого ограничения самих линий по отдельности будет недостаточно. Спасибо!   -  person glutz    schedule 14.12.2011
comment
Извините, что продолжаю спрашивать, я просто упускаю детали: все ли ваши точки соединены друг с другом линиями? Потому что единственный способ получить вещи в прямоугольнике без пересечения с линиями — это создать один прямоугольник, который (едва ли) включает в себя все точки. Кроме того, не могли бы вы отредактировать свой вопрос, чтобы следующий человек, который читает это, понял вашу точку зрения, не прочитав нашу маленькую ветку? ;)   -  person Miquel    schedule 14.12.2011
comment
Может быть, нарисовать картину? Это интересно, но я не могу понять, имеете ли вы в виду N линий, которые пересекаются, образуют многоугольник или что-то в этом роде.   -  person Kit    schedule 14.12.2011
comment
Позвольте мне уточнить. Линии соединены, но конечная точка не соединяется с начальной точкой. Представьте себе 1 поездку по стране. Линия маршрута, например, не соединяет конечные точки и, следовательно, не создает многоугольник.   -  person glutz    schedule 15.12.2011

Ответы (1)


arrow_upward
2
arrow_downward

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

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

C(0, 0) = 0
C(i, 0) = ∞
C(i, j) = min над i' ‹ i из (C(i', j - 1) + [стоимость прямоугольник, покрывающий отрезки i' + 1, …, i])

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

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

person Per    schedule 15.12.2011