Гильотинная перегородка

Гильотинная резка: оптимизированный лист из меньших прямоугольников, который можно разделить в целости и сохранности с помощью правильной серии сквозных разрезов пополам.

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

Гильотинное разделение — это процесс разделения прямолинейного многоугольника , возможно, содержащего несколько отверстий, на прямоугольники с использованием только гильотинных разрезов. ( Разрез гильотиной также называемый разрезом от края до края ) — это прямая делящая линия, идущая от одного края существующего многоугольника к противоположному краю, аналогично гильотине для бумаги .

Гильотинные перегородки особенно распространены при проектировании планов помещений в микроэлектронике . Альтернативный термин для гильотинной перегородки в этом контексте — это разрезная перегородка или разрезной план этажа . ^[1] Гильотинные разделы также являются основной структурой разделов двоичного пространства . Существуют различные проблемы оптимизации, связанные с гильотинным разделением, например: минимизация количества прямоугольников или общей длины разрезов. Это варианты задач разделения полигонов , где разрезы ограничиваются гильотинными разрезами.

Схожая, но другая проблема – резка гильотиной . В этой задаче исходный лист представляет собой простой прямоугольник без отверстий. Проблема заключается в том, что размеры маленьких прямоугольников фиксированы заранее. Целями оптимизации обычно являются максимизация площади производимых прямоугольников или их стоимости или минимизация отходов или количества требуемых листов.

Расчет гильотинной перегородки с наименьшей длиной ребра

В задаче о прямоугольном разбиении минимальной длины ребра цель состоит в том, чтобы разбить исходный прямолинейный многоугольник на прямоугольники так, чтобы общая длина ребра была минимальной. ^[2]^{: 166–167}

Эту проблему можно решить со временем $O(n^{5})$ даже если в необработанном многоугольнике есть дыры. Алгоритм использует динамическое программирование на основе следующего наблюдения: существует гильотинный прямоугольный раздел минимальной длины, в котором каждый максимальный отрезок содержит вершину границы . Таким образом, на каждой итерации $O(n)$ Возможные варианты следующего разреза на гильотине, и вообще есть $O(n^{4})$ подзадачи.

В частном случае, когда все отверстия вырождены (одиночные точки), прямоугольная перегородка гильотины минимальной длины не более чем в 2 раза превышает прямоугольную перегородку минимальной длины. ^[2]^{: 167–170} При более тщательном анализе можно доказать, что коэффициент аппроксимации на самом деле не превышает 1,75. Неизвестно, является ли значение 1,75 точным, но есть случай, когда коэффициент аппроксимации равен 1,5. ^[3] Таким образом, гильотинное разделение обеспечивает аппроксимацию общей задачи с постоянным коэффициентом, которая является NP-трудной.

Эти результаты можно распространить на d -мерный ящик: гильотинный перегородок с минимальной длиной ребра можно найти за время. $O(dn^{2d+1})$ , а полный ( d -1)-объем в оптимальной гильотинной перегородке не превосходит $2d-4+4/d$ раз больше, чем у оптимального раздела d -box. ^[4]

Арора ^[5] и Митчелл ^[6] использовал технику гильотинного разделения для разработки схем аппроксимации с полиномиальным временем для различных задач геометрической оптимизации.

Количество гильотинных перегородок

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

В двух измерениях существует верхняя граница $O\left({\frac {n!2^{5n-3}}{n^{3/2}}}\right)$ приписывают Кнуту . точное число — число Шредера . ^[7]
В измерениях Акерман, Бареке, Пинтер и Ромик. ^[8] дать точную формулу суммирования и доказать, что она находится в $\Theta \left({\frac {(2d-1+2{\sqrt {d(d-1)}})^{n}}{n^{3/2}}}\right)$ . Когда d =2 эта граница становится $\Theta \left({\frac {(3+2{\sqrt {2}})^{n}}{n^{3/2}}}\right)$ .
Асиновски, Бареке, Мансур и Пинтер ^[9] изучите также число классов разрезной эквивалентности гильотинных перегородок.

Покраска гильотинных перегородок

Полихроматическая раскраска планарного графа — это такая раскраска его вершин, при которой в каждой грани графа каждый цвет встречается хотя бы один раз. Некоторые исследователи пытались найти наибольшее k такое, что полихроматическая k -раскраска всегда существует. Важным частным случаем является случай, когда граф представляет собой разбиение прямоугольника на прямоугольники.

Диниц, Кац и Краковски ^[10] доказал, что всегда существует полихроматическая 3-раскраска.
Айгнер-Хорев, Кац, Краковски и Лоффлер ^[11] доказал, что в специальном подслучае, когда граф представляет собой гильотину , всегда существует сильная полихроматическая 4-раскраска.
Кесег ^[12] распространил этот результат на d -мерные гильотинные перегородки и предоставил эффективный алгоритм раскраски.
Димитров, Айгнер-Хорев и Краковски ^[13] наконец доказал, что всегда существует сильная полихроматическая 4-раскраска.

См. также

Разделение двоичного пространства

Ссылки

^ Ленгауэр, Томас (1990), «Разделение схем» , Комбинаторные алгоритмы для компоновки интегральных схем , Висбаден: Vieweg+Teubner Verlag, стр. 251–301, doi : 10.1007/978-3-322-92106-2_6 , ISBN 978-3-322-92108-6 , получено 16 января 2021 г.
^ Jump up to: ^а ^б Ду, Дин-Чжу; Ко, Кер-И.; Ху, Сяодун (2012). Проектирование и анализ алгоритмов аппроксимации . Оптимизация Springer и ее приложения. Нью-Йорк: Springer-Verlag. стр. 165–209, глава 5 «Разрез гильотиной». ISBN 978-1-4614-1700-2 .
^ Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1989 г.). «Улучшенные границы прямоугольных и гильотинных перегородок» . Журнал символических вычислений . 7 (6): 591–610. дои : 10.1016/S0747-7171(89)80042-2 . ISSN 0747-7171 .
^ Гонсалес, Теофило Ф.; Раззази, Мохаммадреза; Шинг, Ман-Так; Чжэн, Си-Цин (1 мая 1994 г.). «Об оптимальных гильотинных перегородках, аппроксимирующих оптимальные перегородки d-box» . Вычислительная геометрия . 4 (1): 1–11. дои : 10.1016/0925-7721(94)90013-2 . ISSN 0925-7721 .
^ Арора, С. (октябрь 1996 г.). «Схемы аппроксимации полиномиальным временем для евклидовой коммерческой задачи и других геометрических задач» . Материалы 37-й конференции по основам информатики . стр. 2–11. дои : 10.1109/SFCS.1996.548458 . ISBN 0-8186-7594-2 . S2CID 1499391 .
^ Митчелл, Джозеф С.Б. (1 января 1999 г.). «Гильотинные подразделения, аппроксимирующие полигональные подразделения: простая схема аппроксимации с полиномиальным временем для геометрического TSP, k-MST и связанных с ним задач» . SIAM Journal по вычислительной технике . 28 (4): 1298–1309. дои : 10.1137/S0097539796309764 . ISSN 0097-5397 .
^ Яо, Бо; Чен, Хунъюй; Ченг, Чунг-Куан; Грэм, Рональд (1 января 2003 г.). «План этажа: сложность и связи» . Труды АСМ по автоматизации проектирования электронных систем . 8 (1): 55–80. дои : 10.1145/606603.606607 . ISSN 1084-4309 . S2CID 1645358 .
^ Акерман, Эяль; Бареке, Гилл; Пинтер, Рон Ю.; Ромик, Дэн (31 мая 2006 г.). «Количество гильотинных перегородок в d измерениях» . Письма об обработке информации . 98 (4): 162–167. дои : 10.1016/j.ipl.2006.01.011 . ISSN 0020-0190 .
^ Асиновский, Андрей; Бареке, Гилл; Мансур, Туфик; Пинтер, Рон Ю. (28 сентября 2014 г.). «Вырезать эквивалентность d-мерных гильотинных перегородок» . Дискретная математика . 331 : 165–174. дои : 10.1016/j.disc.2014.05.014 . ISSN 0012-365X .
^ Диниц, Ефим; Кац, Мэтью Дж.; Краковски, Рой (1 декабря 2009 г.). «Охрана прямоугольных перегородок» . Международный журнал вычислительной геометрии и приложений . 19 (6): 579–594. дои : 10.1142/S0218195909003131 . ISSN 0218-1959 .
^ Хорев, Элад; Кац, Мэтью Дж.; Краковски, Рой; Леффлер, Мартен (15 июня 2009 г.). «Полихроматическая 4-раскраска гильотинных подразделений» . Письма об обработке информации . 109 (13): 690–694. дои : 10.1016/j.ipl.2009.03.006 . ISSN 0020-0190 .
^ Кесег, Балаж (2008). Ху, Сяодун; Ван, Цзе (ред.). «Полихроматические раскраски n-мерных гильотинных перегородок» . Вычисления и комбинаторика . Конспекты лекций по информатике. 5092 . Берлин, Гейдельберг: Springer: 110–118. дои : 10.1007/978-3-540-69733-6_12 . ISBN 978-3-540-69733-6 .
^ Димитров, Дарко; Хорев, Элад; Краковски, Рой (6 мая 2009 г.). «Полихроматические раскраски прямоугольных перегородок» . Дискретная математика . 309 (9): 2957–2960. дои : 10.1016/j.disc.2008.07.035 . ISSN 0012-365X .

[1] Ленгауэр, Томас (1990), «Разделение схем» , Комбинаторные алгоритмы для компоновки интегральных схем , Висбаден: Vieweg+Teubner Verlag, стр. 251–301, doi : 10.1007/978-3-322-92106-2_6 , ISBN 978-3-322-92108-6 , получено 16 января 2021 г.

[:0-2] Jump up to: ^а ^б Ду, Дин-Чжу; Ко, Кер-И.; Ху, Сяодун (2012). Проектирование и анализ алгоритмов аппроксимации . Оптимизация Springer и ее приложения. Нью-Йорк: Springer-Verlag. стр. 165–209, глава 5 «Разрез гильотиной». ISBN 978-1-4614-1700-2 .

[3] Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1989 г.). «Улучшенные границы прямоугольных и гильотинных перегородок» . Журнал символических вычислений . 7 (6): 591–610. дои : 10.1016/S0747-7171(89)80042-2 . ISSN 0747-7171 .

[:6-4] Гонсалес, Теофило Ф.; Раззази, Мохаммадреза; Шинг, Ман-Так; Чжэн, Си-Цин (1 мая 1994 г.). «Об оптимальных гильотинных перегородках, аппроксимирующих оптимальные перегородки d-box» . Вычислительная геометрия . 4 (1): 1–11. дои : 10.1016/0925-7721(94)90013-2 . ISSN 0925-7721 .

[5] Арора, С. (октябрь 1996 г.). «Схемы аппроксимации полиномиальным временем для евклидовой коммерческой задачи и других геометрических задач» . Материалы 37-й конференции по основам информатики . стр. 2–11. дои : 10.1109/SFCS.1996.548458 . ISBN 0-8186-7594-2 . S2CID 1499391 .

[6] Митчелл, Джозеф С.Б. (1 января 1999 г.). «Гильотинные подразделения, аппроксимирующие полигональные подразделения: простая схема аппроксимации с полиномиальным временем для геометрического TSP, k-MST и связанных с ним задач» . SIAM Journal по вычислительной технике . 28 (4): 1298–1309. дои : 10.1137/S0097539796309764 . ISSN 0097-5397 .

[7] Яо, Бо; Чен, Хунъюй; Ченг, Чунг-Куан; Грэм, Рональд (1 января 2003 г.). «План этажа: сложность и связи» . Труды АСМ по автоматизации проектирования электронных систем . 8 (1): 55–80. дои : 10.1145/606603.606607 . ISSN 1084-4309 . S2CID 1645358 .

[8] Акерман, Эяль; Бареке, Гилл; Пинтер, Рон Ю.; Ромик, Дэн (31 мая 2006 г.). «Количество гильотинных перегородок в d измерениях» . Письма об обработке информации . 98 (4): 162–167. дои : 10.1016/j.ipl.2006.01.011 . ISSN 0020-0190 .

[9] Асиновский, Андрей; Бареке, Гилл; Мансур, Туфик; Пинтер, Рон Ю. (28 сентября 2014 г.). «Вырезать эквивалентность d-мерных гильотинных перегородок» . Дискретная математика . 331 : 165–174. дои : 10.1016/j.disc.2014.05.014 . ISSN 0012-365X .

[10] Диниц, Ефим; Кац, Мэтью Дж.; Краковски, Рой (1 декабря 2009 г.). «Охрана прямоугольных перегородок» . Международный журнал вычислительной геометрии и приложений . 19 (6): 579–594. дои : 10.1142/S0218195909003131 . ISSN 0218-1959 .

[11] Хорев, Элад; Кац, Мэтью Дж.; Краковски, Рой; Леффлер, Мартен (15 июня 2009 г.). «Полихроматическая 4-раскраска гильотинных подразделений» . Письма об обработке информации . 109 (13): 690–694. дои : 10.1016/j.ipl.2009.03.006 . ISSN 0020-0190 .

[12] Кесег, Балаж (2008). Ху, Сяодун; Ван, Цзе (ред.). «Полихроматические раскраски n-мерных гильотинных перегородок» . Вычисления и комбинаторика . Конспекты лекций по информатике. 5092 . Берлин, Гейдельберг: Springer: 110–118. дои : 10.1007/978-3-540-69733-6_12 . ISBN 978-3-540-69733-6 .

[13] Димитров, Дарко; Хорев, Элад; Краковски, Рой (6 мая 2009 г.). «Полихроматические раскраски прямоугольных перегородок» . Дискретная математика . 309 (9): 2957–2960. дои : 10.1016/j.disc.2008.07.035 . ISSN 0012-365X .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]