Упаковка прямоугольников в выпуклые многоугольники, но без поворотов

23

Меня интересует проблема упаковки идентичных копий (2-мерных) прямоугольников в выпуклый (2-мерный) многоугольник без перекрытий. В моей задаче вы не можете поворачивать прямоугольники и можете предполагать, что они ориентированы параллельно осям. Вам только что дали размеры прямоугольника и вершины многоугольника и спросили, сколько одинаковых копий прямоугольника может быть упаковано в многоугольник. Если вам разрешено вращать прямоугольники, то, как мне кажется, эта проблема является NP-сложной. Однако что известно, если вы не можете? Как насчет того, чтобы выпуклый многоугольник был просто треугольником? Существуют ли известные алгоритмы аппроксимации, если задача действительно NP-сложная?

Итог пока (21 марта 11 года). Питер Шор замечает, что мы можем рассматривать эту проблему как один из квадратов упаковочных единиц в выпуклом многоугольнике и что эта проблема возникает в NP, если вы накладываете полиномиальную границу на число квадратов / прямоугольников, которые должны быть упакованы. Сариэль Хар-Пелед отмечает, что существует PTAS для того же ограниченного полиномом случая. Однако в общем случае количество упакованных квадратов может быть экспоненциальным по размеру входных данных, которые состоят только из, возможно, короткого списка пар целых чисел. Следующие вопросы кажутся открытыми.

Полная неограниченная версия в NP? Есть ли PTAS для неограниченной версии? Является ли полиномиально ограниченный случай в P или NPC? И мой личный фаворит, легче ли будет проблема, если вы просто ограничитесь упаковкой квадратов в треугольник?

Рафаэль
источник
Упаковка с прямоугольниками 1x3 является NP-полной (с вращением), и я думаю, это станет легко, если мы запретим вращения. Вы найдете максимальное количество прямоугольников для каждой строки (или столбца) и добавите их, чтобы получить общее максимальное количество упакованных прямоугольников.
Мухаммед Аль-Туркистани
Я не уверен, что установка размеров 1x3 (или что-то еще) слишком помогает для моей проблемы, не так ли? Выпуклый многоугольник не обязательно должен иметь какие-либо стороны, параллельные осям, и вам все еще нужно решить, куда поместить прямоугольники. Вы могли бы сначала разместить их ниже по оси Y, а затем выровнять по левому краю как разумную эвристику, но вы можете довольно легко построить примеры там, где это не оптимально.
Рафаэль
9
Вы можете применить аффинное преобразование, чтобы сделать все прямоугольники . Таким образом, проблема эквивалентна проблеме упаковки квадратов. 1×1
Питер Шор
1
@turkistany: Не могли бы вы дать мне ссылку, которая показывает NP-полноту для прямоугольников 1x3? Или это легко наблюдать?
Ёсио Окамото
3
Поиском, основанным на наблюдениях Питера Шора, является maven.smith.edu/~orourke/TOPP/P56.html , что интересно. Однако, похоже, он сфокусирован на простых простых полигонах (то есть они могут быть вогнутыми).
Рафаэль

Ответы:

12

Проблема может быть переформулирована как выбор максимального количества точек внутри выпуклого многоугольника, так что каждая их пара находится на расстоянии (под метрикой ), по крайней мере, 1 друг от друга (просто подумайте о центрах квадратов) , Это, в свою очередь, связано с той же проблемой, когда используется обычное евклидово расстояние. Это, в свою очередь, связано с построением сетки, где каждый заинтересован в разбиении многоугольника на области с хорошим поведением (т. Е. Вы берете диаграмму центров Вороного [см. Центроидальные тесселяции Вороного]).L1

(1ϵ)O(1/ϵ)O(Mnoise(ϵ))Mnoise(ϵ)ϵ

Сариэль Хар-Пелед
источник
Спасибо. Правильно ли я думаю, что даже в случае, когда у нас есть полиномиальная граница для числа прямоугольников / квадратов, все еще не ясно, если проблема в P?
Рафаэль
1
Вот мои 2 цента догадок / предположений ... Было бы удивительно, если бы он был в P - вам нужно было бы показать некоторые дополнительные свойства оптимального решения. Тем не менее, я думаю, что формальное доказательство твердости NP недостижимо - проблема имеет слишком большую структуру. Федер и Грин показали, что кластеризация k-центра является NP-трудной для аппроксимации в пределах определенного фактора. Я думаю / размышляю, что их доказательство может быть использовано, чтобы доказать, что вышеупомянутая проблема является NP-Hard, если у многоугольника есть дыры ...
Сариэль Хар-Пелед
2

Эти две статьи посвящены вашей проблеме:

Э.Г. Биргин и Р.Д. Лобато, " Ортогональная упаковка одинаковых прямоугольников в изотропных выпуклых областях ", Компьютеры и промышленная инженерия 59, с. 595-602, 2010. 

Э.Г. Биргин, Дж.М. Мартинес, Ф.Х. Нишихара и Д.П. Ронкони, « Ортогональная упаковка прямоугольных элементов в произвольных выпуклых областях путем нелинейной оптимизации », Компьютеры и исследования операций 33, с. 3535-3548, 2006.

 

Маркус Ритт
источник
В этих работах рассматривается решение проблемы на практике. Насколько я могу судить, вопрос заключается в том, является ли проблема NP-трудной.
Андрас Саламон
3
Это довольно легко показать, что это в NP. Предположим, я даю вам диаграмму оптимальной упаковки, которая говорит вам, какие квадраты касаются какой стороны многоугольника, а какие квадраты выше / ниже / слева / справа от других квадратов. Вопрос о том, можете ли вы найти координаты для набора квадратов, которые упаковываются именно таким образом, является линейной программой, и поэтому вы можете убедиться, что это диаграмма для выполнимой упаковки.
Питер Шор
4
Если все вершины вашего многоугольника являются целыми числами (или рациональными числами), стандартный результат для линейных программ говорит о том, что вам не нужно больше, чем полиномиальная величина дополнительной точности, и линейная программа может быть решена точно за полиномиальное время. Извините, если вы уже знали это, но я не могу сказать из вашего комментария выше - и даже если вы знали, некоторые люди не будут.
Питер Шор
2
Спасибо. Я знал это однажды, но мне было приятно напомнить. Также кажется, что вы можете иметь экспоненциальное количество квадратов, упакованных в многоугольник, поэтому я не уверен, что вы можете позволить себе перечислить их все. Может быть, есть какое-то масштабирование, которое вы можете сделать, чтобы обойти это?
Рафаэль
3
@Rafael: Я предполагал (без обоснования), что у вас есть полиномиальная оценка числа квадратов. Если вы разрешите экспоненциальные размеры полигонов, все станет намного сложнее.
Питер Шор
1

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

Редактировать: остальная часть этого ответа не применяется, так как отбрасывает явно установленное требование, чтобы все упаковываемые фигуры имели одинаковый размер.


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

  • Собирая квадраты в квадрат, Джозеф Ю.Т. Леунг, Томми В. Там, К. С. Вонг, Гилберт Х. Янг и Фрэнсис Ю. Л. Чин, Журнал параллельных и распределенных вычислений 10 271–275. ( ссылка )

Из бумаги:

мы показываем, что задача квадратной упаковки сильно NP-полна, сводя к ней задачу о 3-разбиениях.

Следовательно, проблема NP-трудна даже для особого случая, когда упаковываемые прямоугольники похожи на контейнер. (В отличие от авторов этой статьи, я не полностью убежден, что проблема в NP, так как позиции, возможно, придется указывать с большой точностью, что может привести к тому, что проверка больше не будет полиномиальной по входному размеру. )

Андраш Саламон
источник
5
Глядя на бумагу, из диаграмм видно, что упаковываемые квадраты не имеют одинаковый размер.
Питер Шор
1
@ Питер: Вы правы, эта статья не имеет ничего общего с проблемой Рафаэля.
Андрас Саламон
0

Может быть, эта статья может быть интересна для вас:

Мозаика многоугольника с прямоугольниками. Автор Kenyon & Kenyon в FOCS 92.

Сильвен Пейроннет
источник
Спасибо. Однако, если я правильно понимаю, плитка точно покрывает многоугольник. Это почти никогда не будет возможно в моем случае (рассмотрим произвольный треугольник в некоторой произвольной ориентации), что, кажется, делает мою проблему оптимизации принципиально иной.
Рафаэль
действительно, это не та же проблема, моя ошибка.
Сильвен Пейроннет
0

Если многоугольник, в который вы хотите упаковать, не обязательно выпуклый, то я думаю, что проблема становится NP-трудной. Вот очень схематичное доказательство. Снижение происходит от некоторой проблемы типа Planar-3-SAT. Для каждой переменной у вас может быть место 1.1 x 1, в зависимости от того, где в этой области вы разместите один квадрат, будет определять, является ли ваша переменная истинной или ложной. Кроме того, если вы покидаете область .1 влево / вправо, то вы можете переместить еще два квадрата внутрь, а также те, что позади них, в конечном итоге предоставив еще одно свободное пространство .1 где-нибудь еще, что вместе теперь влияет на четыре квадрата и так далее. После того, как у вас будет столько копий, сколько вхождений соответствующего литерала, вы подключаете эти трубки к соответствующему компоненту предложения и снова используете некоторый аналогичный гаджет, чтобы гарантировать, что по крайней мере одна из трех входящих трубок должна иметь дополнительный пробел .1.

domotorp
источник
1
Это звучит правдоподобно. Обратите внимание, что Рафаэль предоставил ссылку в комментарии maven.smith.edu/~orourke/TOPP/P56.html с указателем на статью с фактическим сокращением.
Андрас Саламон
О, я не заметил, спасибо.
Домоторп