Разбиение многоугольника

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

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

Термин « полигональная декомпозиция» часто используется как общий термин, включающий как покрытие, так и разбиение. ^[1]

Приложения [ править ]

Многоугольная декомпозиция применяется в нескольких областях: ^[1]

Методы распознавания образов извлекают информацию из объекта, чтобы описать, идентифицировать или классифицировать его. Установленная стратегия распознавания общего многоугольного объекта состоит в том, чтобы разложить его на более простые компоненты, затем идентифицировать компоненты и их взаимосвязи и использовать эту информацию для определения формы объекта.
При обработке данных СБИС макеты представляются в виде многоугольников, и один из подходов к подготовке к электронно-лучевой литографии состоит в том, чтобы разложить эти области многоугольника на фундаментальные фигуры. Разложение по полигонам также используется в процессе разделения области маршрутизации на каналы.
В вычислительной геометрии алгоритмы решения проблем с общими многоугольниками часто более сложными, чем алгоритмы для ограниченных типов многоугольников, таких как выпуклые или звездообразные. Проблема включения точки является одним из примеров. Стратегия решения некоторых из этих типов задач на общих многоугольниках состоит в том, чтобы разложить многоугольник на простые составные части, решить проблему для каждого компонента с помощью специального алгоритма, а затем объединить частичные решения.
Другие приложения включают в себя сжатие данных , системы управления базами данных , обработки изображений и компьютерную графику .

Разбиение многоугольника на треугольники [ править ]

Наиболее хорошо изученная проблема разбиения многоугольника - это разбиение на наименьшее количество треугольников, также называемое триангуляцией . Для многоугольника без отверстий с вершинами триангуляцию можно рассчитать во времени . Для многоугольника с отверстиями существует нижняя граница . ${\ displaystyle n}$ ${\ Displaystyle \ Theta (п)}$ ${\ Displaystyle \ Omega (п \ журнал п)}$

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

Разбиение многоугольника на псевдотреугольники [ править ]

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

Разбиение прямолинейного многоугольника на прямоугольники [ править ]

Особое подсемейство проблем разбиения многоугольника возникает, когда большой многоугольник является прямолинейным многоугольником (также называемым ортогональным многоугольником). В этом случае наиболее важной формой компонента, которую следует учитывать, является прямоугольник . ^[1]

Прямоугольные перегородки имеют множество применений. При проектировании СБИС необходимо разбивать маски на более простые формы, доступные в генераторах литографических узоров, и аналогичные проблемы декомпозиции масок также возникают при проектировании микрочипов ДНК . Прямоугольные разделы могут упростить операции свертки при обработке изображений и могут использоваться для сжатия растровых изображений . Тесно связанные задачи разложения матрицы применялись при планировании лучевой терапии , а прямоугольные перегородки также использовались для разработки последовательностей самосборки роботов . ^[2]

Минимизация количества компонентов [ править ]

Задача минимизации количества составляющих прямоугольников является полиномиальной: известно несколько алгоритмов с полиномиальным временем. См. Обзоры ^[1]^{: 10–13} и ^[2]^{: 3–5} .

Задача разбиения прямолинейного многоугольника на наименьшее количество квадратов (в отличие от произвольных прямоугольников) является NP-сложной . ^[3]

Минимизация общей длины кромки [ править ]

В некоторых случаях более важно минимизировать общую длину разрезов (например, чтобы минимизировать стоимость выполнения перегородки или минимизировать количество пыли). Эта задача называется прямоугольным разбиением с минимальной длиной ребра . Впервые она была изучена Лингасом, Пинтером, Ривестом и Шамиром в 1982 году. ^[4]^[5] Сложность во время выполнения этой проблемы в решающей степени зависит от того, может ли необработанный многоугольник иметь дыры.

Если необработанный многоугольник не содержит отверстий , то оптимальное разбиение может быть найдено за время , где n - количество вершин многоугольника. В частном случае «многоугольника гистограммы» сложность улучшается до . ^[4] Алгоритм использует динамическое программирование и основан на следующем факте: если многоугольник не содержит отверстий, то он имеет разбиение минимальной длины, в котором каждый максимальный линейный сегмент содержит вершину границы. Причина в том, что в любом разделе минимальной длины каждый максимальный линейный сегмент можно «протолкнуть» до тех пор, пока он не достигнет одной из вершин границы, без изменения общей длины. Следовательно, есть только ${\ Displaystyle О (п ^ {4})}$ ${\ Displaystyle О (п ^ {3})}$ ${\ Displaystyle О (п ^ {2})}$ кандидаты на линейный сегмент в оптимальном разделе, и их можно эффективно проверить с помощью динамического программирования. ^[5]^{: 166–167}

Если необработанный многоугольник может иметь дыры , даже если это вырожденные дыры (то есть одиночные точки), проблема NP-трудная. Это может быть доказано сокращением из Planar SAT . ^[4]^[6] Для случая, когда все отверстия являются единственными точками, было разработано несколько приближений постоянного множителя:

A (3 + sqrt (3)) приближение по времени ; ^[6] ${\ Displaystyle О (п ^ {2})}$
A (3 + sqrt (3)) приближение по времени ; ^[7] ${\ Displaystyle О (п \ журнал {п})}$
Приближение 4-го приближения по времени (в более общем плане, в размерностях d , это приближение во времени ), ^[8] ${\ Displaystyle О (п \ журнал {п})}$ ${\ displaystyle 2d}$ ${\ Displaystyle О (дн \ журнал {п})}$
3 приближения по времени ; ${\ Displaystyle О (п ^ {4})}$
1.75 аппроксимация по времени (в более общем смысле, в измерениях d это приближение по времени ); ^[9] последнее приближение использует ограниченный вариант задачи, называемый гильотинным разбиением , в котором разрезы должны быть гильотинными разрезами ( разрезами от края до края). ${\ Displaystyle О (п ^ {5})}$ ${\ displaystyle 2d-4 + 4 / d}$ ${\ displaystyle O (dn ^ {2d + 1})}$
Несколько схем полиномиальной аппроксимации с использованием сложных гильотинных разрезов. ^[10]^[11]^[5]

Разбиение многоугольника на трапеции [ править ]

В системах обработки изображений СБИС часто требуется разделить многоугольную область на минимальное количество трапеций с двумя горизонтальными сторонами. Треугольник с горизонтальной стороной считается трапецией с двумя горизонтальными сторонами, одна из которых вырождена. Для многоугольника без дырок со сторонами такое разбиение наименьшего размера можно найти за время . ^[12] ${\ displaystyle n}$ ${\ Displaystyle О (п ^ {3})}$

Если количество трапеций не должно быть минимальным, трапеция может быть обнаружена во времени как побочный продукт алгоритма триангуляции многоугольника . ^[13] ${\ Displaystyle О (п)}$

Если многоугольник действительно содержит дыры, проблема NP-полная, но можно найти 3-аппроксимацию во времени . ^[12] ${\ Displaystyle О (п \ журнал п)}$

Разбиваем многоугольник на выпуклые четырехугольники [ править ]

Quadrilateralization или quadrangulation является разбиение на четырехугольники .

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

Существуют алгоритмы линейного времени для четырехугольников многоугольников без дырок с точками Штейнера, но они не гарантируют нахождение наименьшего разбиения. ^[14]^[15]

Разбиение многоугольника на m -угольники [ править ]

Обобщением предыдущих задач является разбиение на многоугольники, которые имеют ровно m сторон или не более m сторон. Здесь цель - минимизировать общую длину кромки. Эта проблема может быть решена за время, полиномиальное от n и m . ^[16]^[17]

Разбиение многоугольника на выпуклые многоугольники [ править ]

Задача оптимального выпуклого разбиения состоит в том, чтобы разбить невыпуклый многоугольник на как можно меньше выпуклых многоугольников , используя только исходные вершины многоугольника. Существуют точные и приблизительные алгоритмы решения этой задачи. ^[18]

Более общие формы компонентов [ править ]

Были изучены более общие формы частей, включая спиральные формы, звездообразные многоугольники и монотонные многоугольники . См. ^[1] для обзора.

Разделите выпуклый многоугольник на выпуклые части одинаковой площади и периметра [ править ]

Справедливо многоугольник разбиение проблемы ^[19] является разбиение а (выпуклый) многоугольник в (выпуклые) части с равным периметром и одинаковой площади (это особый случай справедливой торт резки ). Любой выпуклый многоугольник можно легко разрезать на любое количество n выпуклых частей с площадью ровно 1 / n . Однако добиться того, чтобы детали имели одинаковую площадь и равный периметр, сложнее. Существуют алгоритмы решения этой задачи при количестве штук в степени 2. ^[20]

Обобщение этой проблемы состоит в том, что меры площади и периметра заменяются мерой на теле и на границе многоугольника соответственно. Эта проблема прорабатывалась на 2 и 3 штуках. ^[21]

Существует еще одно обобщение, позволяющее обрабатывать любое количество мер.

См. Также [ править ]

Полигональное покрытие - связанная с этим проблема, при которой части могут перекрываться.
Проблема упаковки - связанная проблема, при которой части должны умещаться внутри всего большого объекта, но не должны покрывать его полностью.
Евклидовы мозаики выпуклыми правильными многоугольниками - проблема разбиения всей плоскости на простые многоугольники, такие как прямоугольники .
Возведение квадрата в квадрат - задача разбиения целого квадрата с использованием только других целых квадратов.
Разделение пространства
Тайловая головоломка - головоломка, состоящая из нескольких заданных частей в один большой многоугольник.
Гильотинная перегородка

Ссылки [ править ]

^ Б с д е е Марк Keil, J. (2000). «Разложение многоугольника». Справочник по вычислительной геометрии . С. 491–518. DOI : 10.1016 / B978-044482537-7 / 50012-7 . ISBN 9780444825377.
^ a b c Эппштейн, Дэвид (2010). "Теоретико-графические решения задач вычислительной геометрии". Теоретико-графические концепции в компьютерных науках . Конспект лекций по информатике. 5911 . С. 1–16. CiteSeerX 10.1.1.249.5965 . DOI : 10.1007 / 978-3-642-11409-0_1 . ISBN 978-3-642-11408-3.
^ Realz Slaw. «Замощение прямоугольного многоугольника квадратами» . Обмен стеками CS . Проверено 19 октября 2015 года .
^ a b c Анджей Лингас и Рон И. Пинтер, Рон Л. Ривест и Ади Шамир (1982). «Разбиение по минимальной длине ребер прямолинейных многоугольников» (PDF) . Proc. 20-я Аллертонская конф. Commun. Контрольное вычисление: 53–63.
^ а б в Ду, Дин-Чжу; Ко, Кер-И .; Ху, Сяодун (2012). Разработка и анализ алгоритмов аппроксимации . Оптимизация Springer и ее приложения. Нью-Йорк: Springer-Verlag. С. 165–209, глава 5 «Гильотинная резка». ISBN 978-1-4614-1700-2.
^ a b Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1985 г.). «Границы разбиения прямолинейных многоугольников» . Материалы первого ежегодного симпозиума по вычислительной геометрии . SCG '85. Балтимор, Мэриленд, США: Ассоциация вычислительной техники: 281–287. DOI : 10.1145 / 323233.323269 . ISBN 978-0-89791-163-4.
^ Levcopoulos, С (1986-08-01). «Быстрая эвристика для прямоугольных разбиений многоугольников минимальной длины» . Материалы второго ежегодного симпозиума по вычислительной геометрии . SCG '86. Йорктаун-Хайтс, Нью-Йорк, США: Ассоциация вычислительной техники: 100–108. DOI : 10.1145 / 10515.10526 . ISBN 978-0-89791-194-8.
^ Гонсалес, Теофило Ф .; Раззази, Мохаммадреза; Чжэн, Си-Цин (1993-12-01). «Эффективный алгоритм приближения разделяй и властвуй для разбиения на d-блоки» . Международный журнал вычислительной геометрии и приложений . 03 (04): 417–428. DOI : 10.1142 / S0218195993000269 . ISSN 0218-1959 .
^ Гонсалес, Теофило; Чжэн, Си-Цин (01.06.1989). «Улучшены границы для прямоугольных и гильотинных перегородок» . Журнал символических вычислений . 7 (6): 591–610. DOI : 10.1016 / S0747-7171 (89) 80042-2 . ISSN 0747-7171 .
Перейти ↑ Arora, S. (октябрь 1996 г.). «Полиномиальные схемы аппроксимации для евклидовой ЗК и других геометрических задач» . Материалы 37-й конференции по основам информатики : 2–11. DOI : 10.1109 / SFCS.1996.548458 .
^ Митчелл, Джозеф SB (1999-01-01). «Гильотинное подразделение приближенного многоугольного подразделения: простая схема аппроксимации полиномиального времени для геометрической TSP, k-MST и связанных задач» . SIAM Journal on Computing . 28 (4): 1298–1309. DOI : 10,1137 / S0097539796309764 . ISSN 0097-5397 .
^ a b c Асано, Такао; Асано, Тецуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал ACM . 33 (2): 290. DOI : 10,1145 / 5383,5387 . hdl : 2433/98478 .
^ Chazelle, Bernard (2007). «Триангуляция простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 6 (3): 485–524. DOI : 10.1007 / bf02574703 .
^ Х. Эверетт; В. Ленхарт; М. Овермарс; Т. Шермер; J. Urrutia. (1992). «Строго выпуклые четырехугольники многоугольников». Proc. 4-я канадская. Конф. Comput. Геом . С. 77–83.
^ Рамасвами, Сунита; Рамос, Педро; Туссен, Годфрид (1998). «Преобразование триангуляции в четырехугольник». Вычислительная геометрия . 9 (4): 257. DOI : 10.1016 / s0925-7721 (97) 00019-9 .
^ Лингас, Анджей; Левкопулос, Христос; Мешок, Йорг (1987). «Алгоритмы разбиения полигонов минимальной длины». БИТ . 27 (4): 474. DOI : 10.1007 / bf01937272 .
^ Левкопулос, Христос; Лингас, Анджей; Мешок, Йорг-Р. (1989). «Эвристика для оптимальных деревьев двоичного поиска и задач триангуляции минимального веса». Теоретическая информатика . 66 (2): 181. DOI : 10.1016 / 0304-3975 (89) 90134-5 .
^ Хертель, Стефан; Мельхорн, Курт (1983). Карпинский, Марек (ред.). «Быстрая триангуляция простых полигонов» . Основы теории вычислений . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 207–218. DOI : 10.1007 / 3-540-12689-9_105 . ISBN 978-3-540-38682-7.
^ Nandakumar, R .; Рао, Н. Рамана (август 2012 г.). « „ Перегородки Красивого“многоугольников - Введение» . Труды - Математические науки . 122 (3): 459–467. arXiv : 0812.2241 . DOI : 10.1007 / s12044-012-0076-5 . ISSN 0253-4142 .
^ "Алгоритмы справедливого разбиения выпуклых многоугольников" . Теоретическая информатика . 607 : 351–362. 2015-11-23. DOI : 10.1016 / j.tcs.2015.08.003 . ISSN 0304-3975 .
^ Bespamyatnikh Сергей (2003). Акияма, Джин; Кано, Микио (ред.). «О разделении торта» . Дискретная и вычислительная геометрия . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 60–71. DOI : 10.1007 / 978-3-540-44400-8_7 . ISBN 978-3-540-44400-8.
^ Lingas, Анджей (1982). «Сила непрямолинейных отверстий». Автоматы, языки и программирование . Конспект лекций по информатике. 140 . С. 369–383. DOI : 10.1007 / bfb0012784 . ISBN 978-3-540-11576-2.

[Keil2000-1] Б с д е е Марк Keil, J. (2000). «Разложение многоугольника». Справочник по вычислительной геометрии . С. 491–518. DOI : 10.1016 / B978-044482537-7 / 50012-7 . ISBN 9780444825377.

[Eppstein2009-2] Эппштейн, Дэвид (2010). "Теоретико-графические решения задач вычислительной геометрии". Теоретико-графические концепции в компьютерных науках . Конспект лекций по информатике. 5911 . С. 1–16. CiteSeerX 10.1.1.249.5965 . DOI : 10.1007 / 978-3-642-11409-0_1 . ISBN 978-3-642-11408-3.

[Slaw2013-3] Realz Slaw. «Замощение прямоугольного многоугольника квадратами» . Обмен стеками CS . Проверено 19 октября 2015 года .

[:0-4] Анджей Лингас и Рон И. Пинтер, Рон Л. Ривест и Ади Шамир (1982). «Разбиение по минимальной длине ребер прямолинейных многоугольников» (PDF) . Proc. 20-я Аллертонская конф. Commun. Контрольное вычисление: 53–63.

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

[:3-6] Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1985 г.). «Границы разбиения прямолинейных многоугольников» . Материалы первого ежегодного симпозиума по вычислительной геометрии . SCG '85. Балтимор, Мэриленд, США: Ассоциация вычислительной техники: 281–287. DOI : 10.1145 / 323233.323269 . ISBN 978-0-89791-163-4.

[7] Levcopoulos, С (1986-08-01). «Быстрая эвристика для прямоугольных разбиений многоугольников минимальной длины» . Материалы второго ежегодного симпозиума по вычислительной геометрии . SCG '86. Йорктаун-Хайтс, Нью-Йорк, США: Ассоциация вычислительной техники: 100–108. DOI : 10.1145 / 10515.10526 . ISBN 978-0-89791-194-8.

[8] Гонсалес, Теофило Ф .; Раззази, Мохаммадреза; Чжэн, Си-Цин (1993-12-01). «Эффективный алгоритм приближения разделяй и властвуй для разбиения на d-блоки» . Международный журнал вычислительной геометрии и приложений . 03 (04): 417–428. DOI : 10.1142 / S0218195993000269 . ISSN 0218-1959 .

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

[10] Перейти ↑ Arora, S. (октябрь 1996 г.). «Полиномиальные схемы аппроксимации для евклидовой ЗК и других геометрических задач» . Материалы 37-й конференции по основам информатики : 2–11. DOI : 10.1109 / SFCS.1996.548458 .

[11] Митчелл, Джозеф SB (1999-01-01). «Гильотинное подразделение приближенного многоугольного подразделения: простая схема аппроксимации полиномиального времени для геометрической TSP, k-MST и связанных задач» . SIAM Journal on Computing . 28 (4): 1298–1309. DOI : 10,1137 / S0097539796309764 . ISSN 0097-5397 .

[Asano1986-12] Асано, Такао; Асано, Тецуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал ACM . 33 (2): 290. DOI : 10,1145 / 5383,5387 . hdl : 2433/98478 .

[Chazelle1991-13] Chazelle, Bernard (2007). «Триангуляция простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 6 (3): 485–524. DOI : 10.1007 / bf02574703 .

[Everett1992-14] Х. Эверетт; В. Ленхарт; М. Овермарс; Т. Шермер; J. Urrutia. (1992). «Строго выпуклые четырехугольники многоугольников». Proc. 4-я канадская. Конф. Comput. Геом . С. 77–83.

[Ramaswami1998-15] Рамасвами, Сунита; Рамос, Педро; Туссен, Годфрид (1998). «Преобразование триангуляции в четырехугольник». Вычислительная геометрия . 9 (4): 257. DOI : 10.1016 / s0925-7721 (97) 00019-9 .

[Lingas1987-16] Лингас, Анджей; Левкопулос, Христос; Мешок, Йорг (1987). «Алгоритмы разбиения полигонов минимальной длины». БИТ . 27 (4): 474. DOI : 10.1007 / bf01937272 .

[Levcopoulos1989-17] Левкопулос, Христос; Лингас, Анджей; Мешок, Йорг-Р. (1989). «Эвристика для оптимальных деревьев двоичного поиска и задач триангуляции минимального веса». Теоретическая информатика . 66 (2): 181. DOI : 10.1016 / 0304-3975 (89) 90134-5 .

[18] Хертель, Стефан; Мельхорн, Курт (1983). Карпинский, Марек (ред.). «Быстрая триангуляция простых полигонов» . Основы теории вычислений . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 207–218. DOI : 10.1007 / 3-540-12689-9_105 . ISBN 978-3-540-38682-7.

[19] Nandakumar, R .; Рао, Н. Рамана (август 2012 г.). « „ Перегородки Красивого“многоугольников - Введение» . Труды - Математические науки . 122 (3): 459–467. arXiv : 0812.2241 . DOI : 10.1007 / s12044-012-0076-5 . ISSN 0253-4142 .

[20] "Алгоритмы справедливого разбиения выпуклых многоугольников" . Теоретическая информатика . 607 : 351–362. 2015-11-23. DOI : 10.1016 / j.tcs.2015.08.003 . ISSN 0304-3975 .

[21] Bespamyatnikh Сергей (2003). Акияма, Джин; Кано, Микио (ред.). «О разделении торта» . Дискретная и вычислительная геометрия . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 60–71. DOI : 10.1007 / 978-3-540-44400-8_7 . ISBN 978-3-540-44400-8.

[Lingas1982-22] Lingas, Анджей (1982). «Сила непрямолинейных отверстий». Автоматы, языки и программирование . Конспект лекций по информатике. 140 . С. 369–383. DOI : 10.1007 / bfb0012784 . ISBN 978-3-540-11576-2.

[1]