Для заданного ортогонального многоугольника (многоугольник, стороны которого параллельны осям), я хочу найти наименьший набор внутренних непересекающихся квадратов, объединение которых равно многоугольнику.
Я нашел несколько ссылок на слегка отличающиеся проблемы, такие как:
- Покрытие ортогонального многоугольника квадратами - похоже на мою проблему, но покрывающие квадраты могут перекрываться. Эта проблема имеет полиномиальное решение ( Aupperle, Conn, Keil and O'Rourke, 1988 ; Bar-Yehuda and Ben-Hanoch, 1996 ).
- Черепица / разложение / разбиение ортогонального многоугольника на прямоугольники . Эта проблема имеет полиномиальное решение ( Keil, 2000 ; Eppstein, 2009 ).
- Покрытие ортогонального многоугольника прямоугольниками - известно, что эта задача является NP-полной ( Culberson and Reckhow, 1988 ).
Я ищу алгоритм для минимальной плитки с квадратами .
algorithms
computational-geometry
tiling
Эрель Сегал-Халеви
источник
источник
Ответы:
Я попытаюсь показать, что эта проблема является NP-трудной, путем сокращения от .Планар- 3 -САТ
Снижение отПланар- 3 -САТ
Некоторые основные гаджеты
Гаджеты - это внутренние конфигурации геометрии, которые позволят нам построить ворота для использования в схеме, к которой мы будем сокращать .Планар- 3 -САТ
4X3-гаджет
Этот гаджет имеет два допустимых состояния минимального квадратного разбиения :
Левая 4X3-гаджет . Посередине и справа: два возможных минимально-квадратных состояния разбиения .
5x4-гаджет
Этот гаджет точно такой же, как 4X3-гаджет , только с большими размерами.
Левая 5x4-гаджет . Посередине и справа: два возможных минимально-квадратных состояния разбиения .
конечная точка-гаджет
Слева: каркас конечной точки-гаджета . Центр: Истинная конечная точка. Справа: ложная конечная точка.
гаджет i-wire
Я-проводное устройство коротко для импликации проволоки .
Правила:
Пример:
Вот как это используется:
Рисунок 8,9 , слева: каркасный i-провод через две конечные точки . Справа: Союз.
Теперь, если одна конечная точка находится в правильном состоянии, она переводит другую конечную точку в положение нажатия. Пример:
Слева: квадратная диаграмма перегородок; левый переключатель выключен, «проталкивает» все квадраты вниз по i-проводу и, наконец, нажимает другой переключатель ( конечная точка ). Справа: квадратная диаграмма перегородок; левая конечная точка заполнена, «выталкивает» все квадраты вниз по i-проводу и заставляет конечную точку слева быть «вверх».
Однако это оставляет безусловный случай:
Если мы объединим два i-провода , мы можем получить двустороннее значение, по сути, логическое (не) равенство:
Таким образом, два я-провод может нести полные отношения равенства, так же, как цепь - на самом деле, это является схемой. Мы будем использовать эти пары для построения полезного провода .
i-провода могут быть ориентированы по мере необходимости.
провод
Провод состоит из пары I-проводов , которые подключены к тем же воротам в каждой конечной точке.
Фотографии :
Вверху: A провод .
Левая и правая: Два возможных минимален квадратных перегородочные-состояния из в проволоке . Обратите внимание, что если провод только этой длины, он не сможет сместиться вправо или влево и должен будет разбить один квадрат на более мелкие кусочки.
провода могут быть ориентированы по мере необходимости.
изгиб ворот : изгиб провода
Слева: вид каркаса. Справа: союзный вид.
Обратите внимание на использование 4X3-гаджета . Используется для фиксации красного провода на нечетную длину.
Ниже приведены два возможных состояния минимального квадратного разбиения изгиба:
Слева и справа: два возможных состояния разбиения минимального квадрата-квадрата изгибаемого провода.
Ворота могут быть ориентированы по мере необходимости. Очевидно, что эти ворота могут быть отражены для работы в другом направлении.
Перекос провод
Это легко сдвинуть провод. Каркасная иллюстрация:
именованное значение ворота
Назвали значение ворота , по существу , конечная точка , как ворота с одним контактом провода:
odd-skip-gate : странный пропуск провода
Иногда неудобно иметь только провода нечетной длины. Например:
Как видите, это небольшое расширение немного раздражает. Вот соответствующее решение с использованием шлюза 4X3 :
Итак, превратив это в ворота, мы получим странный пропуск (в каркасе):
Ворота могут быть ориентированы по мере необходимости.
поворотные ворота : скручивание провода
Иногда вы получаете красный и черный i-провода на неправильных сторонах для использования с воротами . В этом случае предусмотрен поворотный затвор для скручивания красного и черного i-проводов в противоположные стороны.
Каркасная иллюстрация:
Убедите себя, что это работает:
Ворота могут быть ориентированы по мере необходимости.
Сплит-ворота : расщепление провода
Расщепление провода, каркаса:
Убедите себя, что это работает:
Примечание. Каждый провод, входящий и выходящий из разветвителя, обязательно должен где-то подключаться к конечной точке, чтобы поддерживать инвариант. Кроме того, вы можете добавить конечные точки к каждой из пар отведений сплиттера.
Ворота могут быть ориентированы по мере необходимости.
не ворота
Не гейт берет провод и выводит провод, который имеет обратное значение. Это в основном поворотные ворота , за исключением того, что они помечают окраску проводов. В не-вентильных выглядит следующим образом :
И вид двух возможных состояний:
Ворота могут быть ориентированы по мере необходимости.
пункт ворота
Для clause-gate мы сначала вводим clause-gadget :
Вот как выглядят ворота:
Объяснение:
Ворота могут быть ориентированы по мере необходимости.
снижение
Наглядное пособие (первоисточник: Terrain Guarding - NP-Hard (PDF) , воспроизведено в тикзе):
Потом:
Почему это работает
графические источники
Вы также можете увидеть увеличенные изображения, удалив суффиксы imgur url "s", "m", "l". Например, Вы можете увидеть увеличенное изображение этого: http://i.stack.imgur.com/6CKlGs.jpg , перейдя по ссылке http://i.stack.imgur.com/6CKlG.jpg . Обратите внимание на пропущенные "s" перед
.jpg
.источник
Однако получающееся покрытие может включать квадраты, которые перекрываются. Вы ищете плитку, где квадраты не могут перекрываться, поэтому ваша проблема не совсем та же.
источник