В геометрии многоугольник P на плоскости называется монотонным относительно прямой L , если каждая прямая , ортогональная L, пересекает границу P не более двух раз. [1]
Аналогично, полигональная цепь C называется монотонной относительно прямой L , если каждая прямая, ортогональная L, пересекает C не более одного раза.
Для многих практических целей это определение может быть расширено, чтобы допустить случаи, когда некоторые ребра P ортогональны L , а простой многоугольник можно назвать монотонным, если отрезок прямой, соединяющий две точки в P и ортогональный L, полностью лежит в P.
Следуя терминологии монотонных функций , предыдущее определение описывает многоугольники , строго монотонные относительно L.
Предположим, что L совпадает с осью x . Тогда крайняя левая и крайняя правая вершины монотонного многоугольника разлагают его границу на две монотонные полигональные цепи , так что при обходе вершин любой цепи в их естественном порядке их X-координаты монотонно увеличиваются или уменьшаются. Фактически, это свойство можно принять за определение монотонного многоугольника, и оно дает многоугольнику его название.
Выпуклый многоугольник монотонен относительно любой прямой, а многоугольник, монотонный относительно любой прямой, является выпуклым.
Известно, что алгоритм линейного времени сообщает обо всех направлениях, в которых заданный простой многоугольник является монотонным. [2] Он был обобщен для сообщения обо всех способах разложения простого многоугольника на две монотонные цепи (возможно, монотонные в разных направлениях.) [3]
На запросы точек в многоугольниках относительно монотонного многоугольника можно ответить за логарифмическое время после линейной предварительной обработки (для поиска самой левой и самой правой вершин). [1]
Монотонный многоугольник можно легко триангулировать за линейное время. [4]
Для заданного набора точек на плоскости битональный тур — это монотонный многоугольник, соединяющий точки. Минимальный периметр битонального тура для заданного набора точек относительно фиксированного направления может быть найден за полиномиальное время с использованием динамического программирования . [5] Легко показать, что такой минимальный битональный тур — это простой многоугольник: пара пересекающихся ребер может быть заменена более короткой непересекающейся парой, сохраняя при этом битоничность нового тура.
Простой многоугольник можно легко разрезать на монотонные многоугольники за время O ( n log n ). Однако, поскольку треугольник является монотонным многоугольником, триангуляция многоугольника фактически является разрезанием многоугольника на монотонные, и ее можно выполнить для простых многоугольников за время O ( n ) с помощью сложного алгоритма. [6] Также известен более простой рандомизированный алгоритм с линейным ожидаемым временем. [7]
Разрезание простого многоугольника на минимальное число равномерно монотонных многоугольников (т.е. монотонных относительно одной и той же прямой) можно выполнить за полиномиальное время. [8]
В контексте планирования движения два непересекающихся монотонных многоугольника можно разделить одним переносом (т. е. существует перенос одного многоугольника, такой, что они разделяются прямой линией в разные полуплоскости), и это разделение можно найти за линейное время. [9]
Многоугольник называется заметаемым , если прямая линия может быть непрерывно перемещена по всему многоугольнику таким образом, что в любой момент ее пересечение с многоугольной областью будет выпуклым множеством. Монотонный многоугольник заметаем прямой, которая не меняет своей ориентации во время заметания. Многоугольник строго заметаем, если никакая часть его области не заметается более одного раза. Оба типа заметаемости распознаются за квадратичное время. [10]
Не существует единого простого обобщения монотонности полигонов на более высокие размерности.
В одном подходе сохраняемым признаком монотонности является линия L. Трехмерный многогранник называется слабо монотонным в направлении L , если все поперечные сечения, ортогональные L, являются простыми многоугольниками. Если поперечные сечения выпуклы, то многогранник называется слабо монотонным в выпуклом смысле . [9] Оба типа могут быть распознаны за полиномиальное время. [10]
В другом подходе сохраненной одномерной чертой является ортогональное направление. Это приводит к понятию многогранной местности в трех измерениях: многогранной поверхности со свойством, что каждая вертикальная (т. е. параллельная оси Z) линия пересекает поверхность не более чем одной точкой или сегментом.