Монотонный многоугольник
В геометрии многоугольник , если каждая линия , 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]
3D
[ редактировать ]Не существует единого прямого обобщения монотонности полигонов на более высокие измерения.
подходе сохранившейся чертой монотонности является линия L. В одном Трехмерный многогранник называется слабо монотонным в направлении L, если все сечения, ортогональные L, являются простыми многоугольниками. Если сечения выпуклые, то многогранник называется слабо монотонным в выпуклом смысле . [9] Оба типа могут быть распознаны за полиномиальное время. [10]
В другом подходе сохраненным одномерным признаком является ортогональное направление. Это порождает понятие многогранной местности в трех измерениях: многогранная поверхность, свойство которой состоит в том, что каждая вертикальная (т. е. параллельная оси Z) линия пересекает поверхность не более чем на одну точку или сегмент.
См. также
[ редактировать ]- Ортогональная выпуклость — для многоугольников, монотонных одновременно по двум взаимно ортогональным направлениям; также обобщение для любого числа фиксированных направлений.
- Звездообразные многоугольники — полярных координатах. аналог монотонных многоугольников в
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Препарата, Франко П .; Шамос, Майкл Ян (1985), Вычислительная геометрия – Введение , Springer-Verlag , ISBN 0-387-96131-3 , 1-е издание; 2-е издание, исправленное и расширенное, 1988 г.:; Русский перевод, 1989 г.
- ^ Препарата, Франко П .; Суповит, Кеннет Дж. (1981), «Проверка монотонности простого многоугольника», Information Processing Letters , 12 (4): 161–164, doi : 10.1016/0020-0190(81)90091-0 .
- ^ Раппапорт, Дэвид; Розенблум, Арнольд (1994), «Формованные и литые многоугольники», Вычислительная геометрия , 4 (4): 219–233, doi : 10.1016/0925-7721(94)90020-5 .
- ^ Фурнье, А .; Монтуно, Д.Ю. (1984), «Триангуляция простых многоугольников и эквивалентные проблемы», ACM Transactions on Graphics , 3 (2): 153–174, doi : 10.1145/357337.357341 , ISSN 0730-0301 , S2CID 33344266
- ^ Введение в алгоритмы , 2-е изд., Т.Х. Кормен , К.Е. Лейзерсон , Р. Ривест и К. Стейн , MIT Press , 2001. Задача 15-1, стр. 364.
- ^ Шазель, Бернар (1991), «Триангуляция простого многоугольника за линейное время», Дискретная и вычислительная геометрия , 6 (3): 485–524, doi : 10.1007/BF02574703 , ISSN 0179-5376
- ^ Амато, Нэнси М .; Гудрич, Майкл Т .; Рамос, Эдгар А. (2001), «Рандомизированный алгоритм триангуляции простого многоугольника за линейное время» , Discrete & Computational Geometry , 26 (2): 245–265, doi : 10.1007/s00454-001-0027-x , ISSN 0179-5376
- ^ Лю, Робин (1988), «О разложении многоугольников на равномерно монотонные части», Information Processing Letters , 27 (2): 85–89, doi : 10.1016/0020-0190(88)90097-X .
- ^ Jump up to: Перейти обратно: а б Туссен, GT ; Эль Гинди, HA (1984), «Разделение двух монотонных многоугольников в линейном времени», Robotica , 2 (4): 215–220, doi : 10.1017/S0263574700008924 , S2CID 21790511 .
- ^ Jump up to: Перейти обратно: а б Бозе, Просенджит ; ван Кревелд, Марк (2005), «Обобщение монотонности: распознавание специальных классов многоугольников и многогранников путем вычисления хороших разверток», Международный журнал вычислительной геометрии и приложений , 15 (6): 591–608, doi : 10.1142/S0218195905001877 , hdl : 1874/24150 .