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

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

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

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

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

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

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

Связанная задача — разбиение на треугольники с наименьшей суммой сторон (триангуляризация с минимальным весом^[англ.]).

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

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

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

Известно несколько алгоритмов полиномиального времени работы для этой задачи, см. статьи Марка Кейла^[4] и Эппштейна^[5] для обзора.

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

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

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

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

Можно поставить задачу о разбиении многоугольника на выпуклые четырёхугольники.

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

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

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

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

• Покрытие многоугольника^[англ.] — связанная задача, в которой части могут накладываться.
• Задача упаковки — связанная задача, в которой части помещаются в больший объект, но полное заполнение этого объекта не обязательно.
• Мозаики из выпуклых правильных многоугольников на евклидовой плоскости — задача деления всей плоскости на простые многоугольники, например замощение прямоугольниками^[англ.].
• Квадрирование квадрата — задача деления квадрата с целочисленной стороной на другие квадраты с целочисленными сторонами.