Несмотря на заголовок вашего вопроса, я думаю, что вы на самом деле ищете минимальное рассечение на прямоугольники прямолинейного многоугольника.(Ссылки Джейсона о минимальном покрытии прямоугольниками, что является совершенно другой проблемой.)
Дэвид Эппштейн обсуждает эту проблему в разделе 3 своей статьи 2010 года об опросе Теоретико-графические решения задач вычислительной геометрии , и он дает хорошее резюме в этот ответ на mathoverflow.net :
Идея состоит в том, чтобы найти максимумчисло непересекающихся диагональных осей, параллельных оси, которые имеют две вогнутые вершины в качестве конечных точек, разбиваются вдоль них, а затем образуют еще одно разбиение для каждой оставшейся вогнутой вершины.Чтобы найти максимальное количество непересекающихся диагональных осей, параллельных, сформируйте график пересечений диагоналей;этот граф является двудольным, поэтому его максимальное независимое множество можно найти за полиномиальное время с помощью методов сопоставления графов.
Вот мой глянец на этом замечательном кратком описании, используя рисунок 2 из статьи Эппштейна.Предположим, у нас есть прямолинейный многоугольник, возможно, с отверстиями.
Когда многоугольник рассекается на прямоугольники, каждая из вогнутых вершин должна встречаться хотя бы одним краем разреза,Таким образом, мы получаем сечение минимум , если как можно больше этих ребер выполняют двойную функцию, то есть они соединяют две вогнутые вершины.
Итак, давайте нарисуем параллельные оси диагоналимежду двумя вогнутыми вершинами, которые полностью содержатся в многоугольнике.(«Ось параллельная» здесь означает «горизонтальная или вертикальная», а диагональ многоугольника - это линия, соединяющая две несмежные вершины.) Мы хотим использовать как можно больше таких линий врассечение до тех пор, пока они не пересекаются.
(Если нет диагональных осей, рассечение является тривиальным - просто сделайте разрез из каждой вогнутой вершины. Илиесли нет пересечений между диагональными осями, то мы используем их все, плюс вырез из каждой оставшейся вогнутой вершины. В противном случае читаем дальше.)
График пересечений наборасегментов линии имеет узел для каждого сегмента линии, и ребро соединяет два узла, если линии пересекаются.Вот график пересечения для диагональных осей:
Это двудольный с вертикальными диагоналями в одной части и горизонтальными диагоналями в другой части,Теперь мы хотим выбрать как можно больше диагоналей, если они не пересекаются.Это соответствует нахождению максимального независимого множества в графе пересечений.
Найти максимальное независимое множество в общем графе - задача NP-сложная, но в частном случае двудольного графа, Теорема Кёнига показывает, что она эквивалентна проблеме поиска максимального соответствия, которая может быть решена за полиномиальное время, например, с помощью алгоритма Хопкрофта-Карпа .У данного графа может быть несколько максимальных совпадений, но подойдет любой из них, так как все они имеют одинаковый размер.В этом примере все максимальные соответствия имеют три пары вершин, например {(2, 4), (6, 3), (7, 8)}:
(Другие максимальные соответствия на этом графике включают {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)};{(1, 3), (2, 4), (7, 8)}.)
Чтобы получить максимальное совпадение с коротвечая минимальное покрытие вершин , примените доказательство теоремы Кенига .В приведенном выше сопоставлении левый набор равен L = {1, 2, 6, 7}, правый набор равен R = {3, 4, 5, 8},и набор несопоставленных вершин в L равен U = {1}.В U есть только один чередующийся путь, а именно 1–3–6, поэтому набор вершин в чередующихся путях равен Z = {1, 3, 6} и минимальнымпокрытие вершины, таким образом, составляет K = ( L \ Z ) ∪ ( R ∩ Z ) = {2, 3, 7}, показано красным ниже, с максимальным независимым набором зеленого цвета:
Если перевести это обратно в проблему рассечения, это означает, что мы можем использовать пять осей- параллельные диагонали в расчленении:
Наконец, сделайте разрез из каждой оставшейся вогнутой вершины, чтобы завершить рассечение:
