Черепица ортогонального многоугольника с квадратами

12

Для заданного ортогонального многоугольника (многоугольник, стороны которого параллельны осям), я хочу найти наименьший набор внутренних непересекающихся квадратов, объединение которых равно многоугольнику.

Я нашел несколько ссылок на слегка отличающиеся проблемы, такие как:

  • Покрытие ортогонального многоугольника квадратами - похоже на мою проблему, но покрывающие квадраты могут перекрываться. Эта проблема имеет полиномиальное решение ( Aupperle, Conn, Keil and O'Rourke, 1988 ; Bar-Yehuda and Ben-Hanoch, 1996 ).
  • Черепица / разложение / разбиение ортогонального многоугольника на прямоугольники . Эта проблема имеет полиномиальное решение ( Keil, 2000 ; Eppstein, 2009 ).
  • Покрытие ортогонального многоугольника прямоугольниками - известно, что эта задача является NP-полной ( Culberson and Reckhow, 1988 ).

Я ищу алгоритм для минимальной плитки с квадратами .

Эрель Сегал-Халеви
источник
ммм, я могу представить, что это NP-хард. Я постараюсь что-то сформулировать.
Реал Слав
1
Версия минимизации с разрешенными отверстиями - NP-Hard, но для односвязных ортогональных многоугольников (т.е. без отверстий) она имеет полиномиальный алгоритм. Однако, если в вашей задаче размеры целочисленные, и вы действительно подразумеваете минимальное покрытие, а не минимальное покрытие, то в этом случае возможен полиномиальный алгоритм.
Пархам
Ммм, мне нужно доказательство того, что минимальные квадраты будут рационально расположены и имеют рациональные размеры; или даже больше, что если вход имеет целочисленный размер и позиционируется как целое число, то минимальные квадраты также будут (чтобы уменьшить его до SAT). Интуитивно, я предполагаю, что это правда, у вас есть идеи, чтобы доказать это?
Реал Слав
@MahmoudAlimohamadi: можете ли вы предоставить названия / авторов статей, в которых изучается (и решается) проблема разбиения прямолинейных многоугольников (с отверстиями или без них) на квадраты?
Вор
2
Кстати, я предполагал, что вы имели в виду минимум ит вместо минимал ал .
Реал Слав

Ответы:

15

Я попытаюсь показать, что эта проблема является NP-трудной, путем сокращения от .Planar-3-SAT


Снижение от Planar-3-SAT

Некоторые основные гаджеты

Гаджеты - это внутренние конфигурации геометрии, которые позволят нам построить ворота для использования в схеме, к которой мы будем сокращать .Planar-3-SAT

4X3-гаджет

Этот гаджет имеет два допустимых состояния минимального квадратного разбиения :

введите описание изображения здесь         введите описание изображения здесь         введите описание изображения здесь

Левая 4X3-гаджет . Посередине и справа: два возможных минимально-квадратных состояния разбиения .

5x4-гаджет

Этот гаджет точно такой же, как 4X3-гаджет , только с большими размерами.

введите описание изображения здесь         введите описание изображения здесь         введите описание изображения здесь

Левая 5x4-гаджет . Посередине и справа: два возможных минимально-квадратных состояния разбиения .

конечная точка-гаджет

TF

введите описание изображения здесь

Слева: каркас конечной точки-гаджета . Центр: Истинная конечная точка. Справа: ложная конечная точка.

гаджет i-wire

Я-проводное устройство коротко для импликации проволоки .

Правила:

  • 22
  • 3

Пример:

введите описание изображения здесь

72

Вот как это используется:

введите описание изображения здесь         введите описание изображения здесь

Рисунок 8,9 , слева: каркасный i-провод через две конечные точки . Справа: Союз.

Теперь, если одна конечная точка находится в правильном состоянии, она переводит другую конечную точку в положение нажатия. Пример:

введите описание изображения здесь         введите описание изображения здесь

Слева: квадратная диаграмма перегородок; левый переключатель выключен, «проталкивает» все квадраты вниз по i-проводу и, наконец, нажимает другой переключатель ( конечная точка ). Справа: квадратная диаграмма перегородок; левая конечная точка заполнена, «выталкивает» все квадраты вниз по i-проводу и заставляет конечную точку слева быть «вверх».

A¬BAB

Однако это оставляет безусловный случай:

введите описание изображения здесь

Если мы объединим два i-провода , мы можем получить двустороннее значение, по сути, логическое (не) равенство:

введите описание изображения здесь         введите описание изображения здесь

Таким образом, два я-провод может нести полные отношения равенства, так же, как цепь - на самом деле, это является схемой. Мы будем использовать эти пары для построения полезного провода .

l12+2

i-провода могут быть ориентированы по мере необходимости.

провод

Провод состоит из пары I-проводов , которые подключены к тем же воротам в каждой конечной точке.

  • В I-провода окрашены в красный и зеленый.
  • 3
  • Каждый штифт затвора будет иметь зеленый и красный контакт; провод должен правильно подключаться.
  • Правило инварианта: один i-провод толкается в противоположном направлении другого i-провода , каждый вентиль принимает это и в этом уверен (если не указано иное).
  • Поскольку каждый провод имеет двустороннее значение, он переносит значения от затвора к затвору, как провод в цепи.
  • Каждый провод должен быть подключен к воротам на обоих концах. , Если это не удастся, это может разрушить допущения некоторых описываемых мною гейтов и правило инварианта выше; однако ворота, у которых есть конечные точки через выводы , безопасны - вы можете подключить к этим конечным точкам паразитные провода, не беспокоясь о том, что это разрушит ворота.
  • провода должны быть нечетной длины, включая провода к любой цепи, к которой он подключается; однако ниже я опишу нечетный пропуск, который позволяет проволоке с четной длиной становиться нечетной.

Фотографии :

введите описание изображения здесь

Вверху: A провод .

введите описание изображения здесь        введите описание изображения здесь

Левая и правая: Два возможных минимален квадратных перегородочные-состояния из в проволоке . Обратите внимание, что если провод только этой длины, он не сможет сместиться вправо или влево и должен будет разбить один квадрат на более мелкие кусочки.

провода могут быть ориентированы по мере необходимости.

изгиб ворот : изгиб провода

введите описание изображения здесь       введите описание изображения здесь

Слева: вид каркаса. Справа: союзный вид.

Обратите внимание на использование 4X3-гаджета . Используется для фиксации красного провода на нечетную длину.

Ниже приведены два возможных состояния минимального квадратного разбиения изгиба:

введите описание изображения здесь         введите описание изображения здесь

Слева и справа: два возможных состояния разбиения минимального квадрата-квадрата изгибаемого провода.

Ворота могут быть ориентированы по мере необходимости. Очевидно, что эти ворота могут быть отражены для работы в другом направлении.

Перекос провод

Это легко сдвинуть провод. Каркасная иллюстрация:

введите описание изображения здесь

именованное значение ворота

Назвали значение ворота , по существу , конечная точка , как ворота с одним контактом провода:

введите описание изображения здесь

odd-skip-gate : странный пропуск провода

Иногда неудобно иметь только провода нечетной длины. Например:

введите описание изображения здесь

Как видите, это небольшое расширение немного раздражает. Вот соответствующее решение с использованием шлюза 4X3 :

введите описание изображения здесь

Итак, превратив это в ворота, мы получим странный пропуск (в каркасе):

введите описание изображения здесь

Ворота могут быть ориентированы по мере необходимости.

поворотные ворота : скручивание провода

Иногда вы получаете красный и черный i-провода на неправильных сторонах для использования с воротами . В этом случае предусмотрен поворотный затвор для скручивания красного и черного i-проводов в противоположные стороны.

Каркасная иллюстрация:

введите описание изображения здесь

Убедите себя, что это работает:

введите описание изображения здесь         введите описание изображения здесь

A

Ворота могут быть ориентированы по мере необходимости.

Сплит-ворота : расщепление провода

Расщепление провода, каркаса:

введите описание изображения здесь

Убедите себя, что это работает:

введите описание изображения здесь

A

введите описание изображения здесь

A

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

Ворота могут быть ориентированы по мере необходимости.

не ворота

Не гейт берет провод и выводит провод, который имеет обратное значение. Это в основном поворотные ворота , за исключением того, что они помечают окраску проводов. В не-вентильных выглядит следующим образом :

введите описание изображения здесь

И вид двух возможных состояний:

введите описание изображения здесь         введите описание изображения здесь

Ворота могут быть ориентированы по мере необходимости.

пункт ворота

Для clause-gate мы сначала вводим clause-gadget :

введите описание изображения здесь

3

Вот как выглядят ворота:

3

Объяснение:

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

3-CNF

Ворота могут быть ориентированы по мере необходимости.

снижение

Φ(x)Planar-3-SAT

Φ(x)=inCi,C={(xjxkxl)}

Наглядное пособие (первоисточник: Terrain Guarding - NP-Hard (PDF) , воспроизведено в тикзе):

введите описание изображения здесь

Потом:

  1. xixxi¬xi
  2. Соедините ворота друг с другом с помощью not-gate , чтобы они логически отрицали значения друг друга.
  3. Поместите полигоны переменных "gates" в их положения в планарном встраивании.
  4. Для каждого предложения поместите ворота предложения в месте расположения предложения в планарном встраивании.
  5. Используя ворота, описанные выше, соедините все переменные с их предложениями.
  6. Запустите алгоритм минимального квадрата-разбиения для результирующего объединения всех многоугольников гейта (всей схемы).
  7. Если алгоритм возвращает сумму всех размеров состояния минимального квадрата разбиения затвора (вычитая для общих углов), то он выполним. Если это не выполнимо, оно заставит ограниченный гаджет разделиться на меньшие квадраты, увеличивая таким образом количество квадратов, необходимых для разделения схемы.

Почему это работает

  • Каждый гаджет имеет минимальный квадратный размер состояния раздела ; то есть минимальное квадратное разбиение этого гаджета имеет определенный размер.
  • Некоторые гаджеты имеют несколько состояний с таким размером; каждое из этих состояний является допустимым минимально-квадратным разбиением .
  • Когда гаджеты объединяются только в углах, сумма состояний минимального квадрата разбиения гаджетов * все еще остается минимальным состоянием разбиения квадрата их объединения; Вы можете видеть это интуитивно: соединение в углу не дает достаточно места для квадрата, чтобы расширяться / соединяться с квадратом из другого гаджета.
  • В то время как объединение гаджетов на углу не уменьшает общий размер минимальной квадратных разделов , он имеет отношение и ограничить гаджеты с каждым-другой.
  • С помощью показанных выше вентилей вы можете достаточно ограничить состояния, чтобы, если логическая формула была неудовлетворительной, то одному или нескольким гадетам пришлось бы разбиваться на еще меньшие квадраты и увеличивать размер минимального разбиения квадрата .

графические источники

Вы также можете увидеть увеличенные изображения, удалив суффиксы imgur url "s", "m", "l". Например, Вы можете увидеть увеличенное изображение этого: http://i.stack.imgur.com/6CKlGs.jpg , перейдя по ссылке http://i.stack.imgur.com/6CKlG.jpg . Обратите внимание на пропущенные "s" перед .jpg.

Реал Слав
источник
3
Вау, это абсолютно впечатляет. К сожалению, я не достаточно умен, чтобы проверить сокращение, но я верю вашему слову :) Спасибо!
Эрель Сегал-Халеви
1
Таким образом, ситуация в мозаике является противоположностью ситуации в покрытии: в покрытии квадратное покрытие является полиномиальным, а прямоугольное покрытие - NP-жестким, в то время как в мозаичном покрытии квадратное покрытие является NP-жестким, а прямоугольное покрытие - полиномиальным.
Эрель Сегал-Халеви
Некоторые дополнительные вопросы, чтобы попытаться доказать, что гаджеты, которые я использую, действительно имеют минимальный квадрат: Как доказать, что минимальное квадратное разбиение прямоугольника 3X2 имеет 3 квадрата | Каково минимальное квадратное разбиение почти квадратного прямоугольника? | Минимальные квадратные перегородки для прямоугольников 4х3 и 5х4 .
Реал Слав
8

NO(N3/2)

«Покрытие ортогональных многоугольников квадратами». LJ Aupperle и Его Превосходительство Конн и JM Keil и Джозеф О'Рурк. Proc. 26th Allerton Conf. Commun. Управляющий компьютер , стр. 97-106, 1988. ( ссылка на скачивание PDF сканирования )

Однако получающееся покрытие может включать квадраты, которые перекрываются. Вы ищете плитку, где квадраты не могут перекрываться, поэтому ваша проблема не совсем та же.

Джозеф О'Рурк
источник
LOL Я был на полпути к формулировке :(. Очень интересно, хотя! Добро пожаловать в cs.SE.
Realz Slaw
2
Если я правильно понимаю, эта статья позволяет квадратам перекрываться (т.е. это проблема покрытия). Меня интересует случай, когда квадраты не могут перекрываться (т.е. это проблема разбиения / разбиения).
Эрель Сегал-Халеви
@ErelSegalHalevi: Извините, я не внимательно прочитал ваш вопрос.
Джозеф О'Рурк
2
О, тогда я продолжу: D
Realz Slaw