У геометрії, многокутник P на площині називають монотонним щодо прямої L, якщо кожна лінія ортогональна до L перетинала P щонайбільше двічі.
Подібно, ламану C звуть монотонною щодо прямої L, якщо кожна лінія ортогональна з L перетинає C щонайбільше раз.
Для багатьох практичних цілей це визначення можна розширити, щоб дозволити випадки коли деякі ребра P ортогональні з L, і простий многокутник можна назвати монотонним якщо відрізок прямої, що поєднує дві точки в P і є ортогональним з L повністю належить P.
Властивості Якщо припустити, що L збігається з віссю x. Тоді найлівіша і найправіша вершини монотонного многокутника розбивають його границю на дві монотонні ламані, такі що коли вершини будь-якої ламаної перебирати в їхньому природному порядку, то їхні x-координати монотонно зростають або спадають. Насправді, цю властивість можна взяти за визначення монотонного многокутника і вона дає йому свої ім'я.
Опуклий многокутник є монотонним щодо будь-якої прямої і многокутник монотонний щодо будь-якої прямої є опуклим.
Відомий алгоритм лінійного часу, що видає всі напрямки у яких певний простий многокутник є монотонним.. Його узагальнили так, щоб він повідомляв усі способи розкладення простого многокутника на дві монотонні ламані (можливо монотонні в різних напрямках.).
Запити на належність точки многокутнику у випадку монотонного многокутника можна обробити за логарифмічний час після передобробітку лінійного часу (щоб знайти найлівішу і найправішу вершини).
Монотонний полігон можна легко тріангулювати за лінійний час за допомогою алгоритму і Д. Я. Монтуно, або алгоритмом .Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," Pattern Recognition Letters, 2 (March):155–158.
Простий полігон можна легко розбити на монотонні полігони за час O(n log n). Однак, оскільки трикутник це монотонний многокутник, то тріангуляція многокутника розбиває многокутник на монотонні многокутники, і, у випадку простого многокутника, її можна зробити за час O(n).
Примітки