Wielokąt monotoniczny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Dwa górne wielokąty są monotoniczne. Zielone proste mają jedno przecięcie z wielokątem, niebieskie - dwa, czerwone - trzy i więcej.

Wielokąt monotoniczny − w geometrii wielokąt, dla którego można wskazać prostą L (tzw. kierunek monotoniczności), taką że każda prosta prostopadła do niej przecina wielokąt w najwyżej dwóch punktach (silna monotoniczność), można również rozszerzyć tę definicję na wielokąty posiadające krawędzie prostopadłe do L (słaba monotoniczność).

Wielokąty wypukłe są monotoniczne w każdym kierunku, natomiast dla wielokąta monotonicznego możliwe jest znalezienie wszystkich jego kierunków monotoniczności w czasie liniowym ze względu na liczbę wierzchołków (O(n)).

Wielokąty tego typu mają duże znaczenie w geometrii obliczeniowej, ponieważ:

  1. W czasie liniowym można dokonać ich triangulacji.
  2. W czasie liniowym można znaleźć łańcuchy krawędzi górny i dolny ze względu na L; następnie w czasie logarytmicznym (O(\log n)) stwierdzić, czy punkt należy do wielokąta.

Ponadto istnieje algorytm, który pozwala w czasie liniowym rozłożyć dowolny wielokąt na sumę wielokątów monotonicznych.


Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Franco P. Preparata, Michael Ian Shamos: Geometria obliczeniowa : wprowadzenie. Gliwice: Helion, 2003, s. 58. ISBN 83-7361-098-7.
  • Mark de Berg: Geometria obliczeniowa : algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 58-70. ISBN 978-83-204-3244-2.