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

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

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

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

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

$(1-\epsilon)$$O(1/\epsilon)$$O(M*noise(\epsilon))$$M$$noise(\epsilon)$$\epsilon$

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

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

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

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

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

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

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

Из бумаги:

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

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

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

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

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