Многоугольный раздел

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Минимизация общей длины ребра

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

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

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

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

Минимизация количества заготовок

В этом случае большой многоугольник уже содержит несколько попарно непересекающихся прямоугольников. Цель состоит в том, чтобы найти разбиение многоугольника на прямоугольники так, чтобы каждый исходный прямоугольник содержался в одном из кусков, при этом количество «заготовок» (кусков, не содержащих исходного прямоугольника) было минимально возможный. Известны следующие результаты: ^[12]

Если большой многоугольник представляет собой прямоугольник, то в любом максимальном расположении n прямоугольников все отверстия являются прямоугольниками, и их число не более $n-\lceil 2{\sqrt {n}}-1\rceil$ , а это туго.
Если большой многоугольник представляет собой прямолинейный многоугольник с T рефлекторными вершинами, то при любом максимальном расположении n прямоугольников дырки можно разбить не более чем на $T+n-\lceil 2{\sqrt {n}}-1\rceil$ прямоугольники, а это туго.

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

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

Если количество трапеций не обязательно должно быть минимальным, трапецию можно найти за время. $O(n)$ , как побочный продукт алгоритма триангуляции полигонов . ^[14]

Если в многоугольнике есть дырки, задача NP-полная, но за время можно найти 3-приближение. $O(n\log n)$ . ^[13]

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

Четырехугольник — или четырехугольник это разбиение на четырехугольники .

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

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

Разбить многоугольник на m -угольников

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

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

При разбиении общего многоугольника на выпуклые многоугольники изучалось несколько целей.

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

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

Минимизация количества заготовок

Исходный многоугольник уже содержит несколько попарно непересекающихся выпуклых фигур, и цель состоит в том, чтобы разбить его на выпуклые многоугольники так, чтобы каждая исходная фигура содержалась в одном из кусочков, и с учетом этого количество «заготовок» (кусков, которые не содержат исходного рисунка) является как можно меньшим. Если большой многоугольник выпуклый, то в любом максимальном расположении n выпуклых фигур все дырки выпуклые и их число не более $2n-5$ , а это туго. ^[12]

Выравнивание площади и периметра

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

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

Существует дальнейшее обобщение для обработки любого количества мер.

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

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

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Марк Кейл, Дж. (2000). «Разложение полигонов». Справочник по вычислительной геометрии . стр. 491–518. дои : 10.1016/B978-044482537-7/50012-7 . ISBN 9780444825377 .
^ Jump up to: ^а ^б Эппштейн, Дэвид (2010). «Теоретико-графовые решения задач вычислительной геометрии». Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 5911. стр. 1–16. CiteSeerX 10.1.1.249.5965 . дои : 10.1007/978-3-642-11409-0_1 . ISBN 978-3-642-11408-3 . S2CID 16353114 .
^ Реалз Слав. «Замощение ортогонального многоугольника квадратами» . Обмен стеком CS . Проверено 19 октября 2015 г.
^ Jump up to: ^а ^б ^с Анджей Лингас, Рон И. Пинтер, Рон Л. Ривест и Ади Шамир (1982). «Разбиение прямолинейных многоугольников по минимальной длине ребра» (PDF) . Учеб. 20-я Аллертонская конференция. Коммун. Управляющий компьютер : 53–63.
^ Jump up to: ^а ^б ^с Ду, Дин-Чжу; Ко, Кер-И.; Ху, Сяодун (2012). Проектирование и анализ алгоритмов аппроксимации . Оптимизация Springer и ее приложения. Нью-Йорк: Springer-Verlag. стр. 165–209, глава 5 «Разрез гильотиной». ISBN 978-1-4614-1700-2 .
^ Jump up to: ^а ^б Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1985 г.). «Границы разбиения прямолинейных многоугольников» . Материалы первого ежегодного симпозиума по вычислительной геометрии - SCG '85 . Балтимор, Мэриленд, США: Ассоциация вычислительной техники. стр. 281–287. дои : 10.1145/323233.323269 . ISBN 978-0-89791-163-4 . S2CID 12588297 .
^ Левкопулос, Ц (1 августа 1986 г.). «Быстрая эвристика для прямоугольных разбиений многоугольников минимальной длины». Материалы второго ежегодного симпозиума по вычислительной геометрии - SCG '86 . Йорктаун-Хайтс, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 100–108. дои : 10.1145/10515.10526 . ISBN 978-0-89791-194-8 . S2CID 16106423 .
^ Гонсалес, Теофило Ф.; Раззази, Мохаммадреза; Чжэн, Си-Цин (1 декабря 1993 г.). «Эффективный алгоритм аппроксимации «разделяй и властвуй» для разделения на d-блоки» . Международный журнал вычислительной геометрии и приложений . 03 (4): 417–428. дои : 10.1142/S0218195993000269 . ISSN 0218-1959 .
^ Гонсалес, Теофило; Чжэн, Си-Цин (1 июня 1989 г.). «Улучшенные границы прямоугольных и гильотинных перегородок» . Журнал символических вычислений . 7 (6): 591–610. дои : 10.1016/S0747-7171(89)80042-2 . ISSN 0747-7171 .
^ Арора, С. (октябрь 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 .
^ Jump up to: ^а ^б Акопян, Арсений; Сегал-Халеви, Эрель (01 января 2018 г.). «Счет заготовок в многоугольных композициях» . SIAM Journal по дискретной математике . 32 (3): 2242–2257. arXiv : 1604.00960 . дои : 10.1137/16M110407X . ISSN 0895-4801 . S2CID 123397485 .
^ Jump up to: ^а ^б Асано, Такао; Асано, Тецуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал АКМ . 33 (2): 290. дои : 10.1145/5383.5387 . hdl : 2433/98478 . S2CID 15296037 .
^ Шазель, Бернар (2007). «Триангуляция простого многоугольника за линейное время» . Дискретная и вычислительная геометрия . 6 (3): 485–524. дои : 10.1007/bf02574703 .
^ Х. Эверетт; В. Ленхарт; М. Овермарс; Т. Шермер; Дж. Уррутиа. (1992). «Строго выпуклые четырехугольники многоугольников». Учеб. 4-я Канада. Конф. Вычислить. Геом . стр. 77–83.
^ Рамасвами, Сунита; Рамос, Педро; Туссен, Годфрид (1998). «Преобразование триангуляций в четырехугольники» . Вычислительная геометрия . 9 (4): 257. дои : 10.1016/s0925-7721(97)00019-9 .
^ Лингас, Анджей; Левкопулос, Христос; Сак, Йорг (1987). «Алгоритмы разбиения многоугольников минимальной длины». КУСОЧЕК . 27 (4): 474. doi : 10.1007/bf01937272 . S2CID 30936524 .
^ Левкопулос, Христос; Лингас, Анджей; Зак, Йорг-Р. (1989). «Эвристика для оптимальных двоичных деревьев поиска и задачи триангуляции с минимальным весом» . Теоретическая информатика . 66 (2): 181. дои : 10.1016/0304-3975(89)90134-5 .
^ Хертель, Стефан; Мельхорн, Курт (1983). «Быстрая триангуляция простых многоугольников». В Карпински, Марек (ред.). Основы теории вычислений . Конспекты лекций по информатике. Том. 158. Берлин, Гейдельберг: Шпрингер. стр. 207–218. дои : 10.1007/3-540-12689-9_105 . ISBN 978-3-540-38682-7 .
^ Нандакумар, Р.; Рао, Н. Рамана (август 2012 г.). « «Справедливое» разбиение многоугольников - введение». Труды - Математические науки . 122 (3): 459–467. arXiv : 0812.2241 . дои : 10.1007/s12044-012-0076-5 . ISSN 0253-4142 . S2CID 189909962 .
^ Армаселу, Богдан; Даеску, Овидиу (23 ноября 2015 г.). «Алгоритмы справедливого разбиения выпуклых многоугольников» . Теоретическая информатика . 607 : 351–362. дои : 10.1016/j.tcs.2015.08.003 . ISSN 0304-3975 .
^ Беспамятных, Сергей (2003). «О разделке торта». В Акияме, Джин; Кано, Микио (ред.). Дискретная и вычислительная геометрия: Японская конференция, JCDCG 2002, Токио, Япония, 6-9 декабря 2002 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 2866. Берлин, Гейдельберг: Springer. стр. 60–71. дои : 10.1007/978-3-540-44400-8_7 . ISBN 978-3-540-44400-8 .

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

[Eppstein2009-2] Jump up to: ^а ^б Эппштейн, Дэвид (2010). «Теоретико-графовые решения задач вычислительной геометрии». Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 5911. стр. 1–16. CiteSeerX 10.1.1.249.5965 . дои : 10.1007/978-3-642-11409-0_1 . ISBN 978-3-642-11408-3 . S2CID 16353114 .

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

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

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

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

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

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

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

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

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

[:4-12] Jump up to: ^а ^б Акопян, Арсений; Сегал-Халеви, Эрель (01 января 2018 г.). «Счет заготовок в многоугольных композициях» . SIAM Journal по дискретной математике . 32 (3): 2242–2257. arXiv : 1604.00960 . дои : 10.1137/16M110407X . ISSN 0895-4801 . S2CID 123397485 .

[Asano1986-13] Jump up to: ^а ^б Асано, Такао; Асано, Тецуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал АКМ . 33 (2): 290. дои : 10.1145/5383.5387 . hdl : 2433/98478 . S2CID 15296037 .

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

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

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

[Lingas1987-17] Лингас, Анджей; Левкопулос, Христос; Сак, Йорг (1987). «Алгоритмы разбиения многоугольников минимальной длины». КУСОЧЕК . 27 (4): 474. doi : 10.1007/bf01937272 . S2CID 30936524 .

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

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

[20] Нандакумар, Р.; Рао, Н. Рамана (август 2012 г.). « «Справедливое» разбиение многоугольников - введение». Труды - Математические науки . 122 (3): 459–467. arXiv : 0812.2241 . дои : 10.1007/s12044-012-0076-5 . ISSN 0253-4142 . S2CID 189909962 .

[21] Армаселу, Богдан; Даеску, Овидиу (23 ноября 2015 г.). «Алгоритмы справедливого разбиения выпуклых многоугольников» . Теоретическая информатика . 607 : 351–362. дои : 10.1016/j.tcs.2015.08.003 . ISSN 0304-3975 .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]