Monotónní mnohoúhelník - Monotone polygon

Zelená označuje jednu křižovatku, modrá označuje dvě křižovatky a červená označuje tři nebo více. Horní dva polygony jsou monotónní vzhledem k L, zatímco spodní dva nejsou.

v geometrie, a polygon P v rovině se nazývá monotónní s ohledem na přímku L, pokud je každý řádek kolmý na L protíná se P maximálně dvakrát.[1]

Podobně, a polygonální řetěz C je nazýván monotónní s ohledem na přímku L, pokud je každý řádek kolmý na L protíná se C maximálně jednou.

Z mnoha praktických důvodů může být tato definice rozšířena, aby umožnila případy, kdy jsou některé hrany P jsou kolmé na La jednoduchý mnohoúhelník lze nazvat monotónní, pokud úsečka spojuje dva body P a je kolmý na L zcela patří P.

Podle terminologie pro monotónní funkce, popisuje dřívější definice polygony přísně monotónní s ohledem na L. Část „s ohledem na“ je nezbytná pro rozlišení striktního / nestriktního rozlišení: mnohoúhelník nestejně monotónní s ohledem na L je striktně monotónní vzhledem k linii L1 otočeno z L o dostatečně malý úhel.

Vlastnosti

Předpokládat, že L se shoduje s X-osa. Potom vrcholy nejvíce vlevo a úplně vpravo monotónního polygonu rozloží jeho hranici na dva monotónní polygonální řetězce takové, že když se vrcholy libovolného řetězce procházejí v jejich přirozeném pořadí, jejich souřadnice X jsou monotónně zvýšení nebo snížení. Ve skutečnosti lze tuto vlastnost použít pro definici monotonního polygonu a dává polygonu jeho název.

A konvexní mnohoúhelník je monotónní vzhledem k libovolné přímce a polygon, který je monotónní vzhledem ke každé přímce, je konvexní.

Je známo, že lineární časový algoritmus hlásí všechny směry, ve kterých je daný jednoduchý polygon monotónní.[2] Bylo zobecněno na hlášení všech způsobů, jak rozložit jednoduchý polygon na dva monotónní řetězce (možná monotónní v různých směrech).[3]

Bod v mnohoúhelníku na dotazy týkající se monotónního polygonu lze odpovědět v logaritmický čas po lineární čas předzpracování (k vyhledání vrcholů zcela vlevo a vpravo).[1]

Monotónní mnohoúhelník může být snadno trojúhelníkové v lineárním čase.[4]

Pro danou sadu bodů v rovině a bitonické turné je monotónní mnohoúhelník, který spojuje body. Minimum obvod bitonickou prohlídku pro daný bod nastavený vzhledem k pevnému směru najdete v polynomiální čas použitím dynamické programování.[5] Je snadné ukázat, že taková minimální bitonická prohlídka je jednoduchý mnohoúhelník: dvojici křížení hran lze nahradit kratší nepřekříženou dvojicí při zachování bitonicity nové prohlídky.

Rozdělení mnohoúhelníku na monotónní mnohoúhelníky

Jednoduchý mnohoúhelník může být snadno nakrájíme na monotónní polygony v Ó(n logn) čas. Jelikož je však trojúhelník monotónní mnohoúhelník, polygon triangulace ve skutečnosti rozřezává mnohoúhelník na monotónní a může být proveden pro jednoduché polygony v Ó(n) čas.[Citace je zapotřebí ]

Řezání jednoduchého polygonu na minimální počet rovnoměrně monotónních polygonů (tj. Monotónních vzhledem ke stejné linii) lze provést v polynomiálním čase.[6]

V kontextu plánování pohybu, dva neprotínající se monotónní polygony lze oddělit jediným překladem (tj. existuje překlad jednoho polygonu tak, že se dva oddělují přímkou ​​do různých polorovin) a toto oddělení lze najít v lineárním čase.[7]

Zobecnění

Zametatelné polygony

Polygon se nazývá zametatelné, pokud lze přímku nepřetržitě přesouvat po celém polygonu takovým způsobem, že v každém okamžiku je její průsečík s polygonální oblastí konvexní množina. Monotónní mnohoúhelník lze zamést čarou, která během tažení nemění svou orientaci. Mnohoúhelník je přísně zametatelné pokud žádná část jeho oblasti není zametena více než jednou. Oba typy zametatelnosti jsou rozpoznány v kvadratickém čase.[8]

3D

Neexistuje jediná přímá generalizace polygonové monotónnosti do vyšších dimenzí.

V jednom přístupu je zachovanou vlastností monotónnosti linie L. Volá se trojrozměrný mnohostěn slabě monotónní ve směru L pokud jsou všechny průřezy kolmé na L jsou jednoduché polygony. Pokud jsou průřezy konvexní, pak se nazývá mnohostěn slabě monotónní v konvexním smyslu.[7] Oba typy lze rozpoznat v polynomiálním čase.[8]

V jiném přístupu je zachovaným jednorozměrným znakem ortogonální směr. To dává vzniknout pojmu polyedrický terén ve třech rozměrech: polyedrický povrch s vlastností, že každá svislá (tj. rovnoběžná s osou Z) přímka protíná povrch nanejvýš o jeden bod nebo segment.

Viz také

Reference

  1. ^ A b Preparata, Franco P.; Shamos, Michael Ian (1985), Výpočetní geometrie - úvod, Springer-Verlag, ISBN  0-387-96131-3, 1. vydání:; 2. tisk, opraveno a rozšířeno, 1988:; Ruský překlad, 1989:CS1 maint: extra interpunkce (odkaz)
  2. ^ Preparata, Franco P.; Supowit, Kenneth J. (1981), „Testování jednoduchého polygonu na monotónnost“, Dopisy o zpracování informací, 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0.
  3. ^ Rappaport, David; Rosenbloom, Arnold (1994), „Tvarovatelné a odlévatelné polygony“, Výpočetní geometrie, 4 (4): 219–233, doi:10.1016/0925-7721(94)90020-5.
  4. ^ Fournier, A.; Montuno, D. Y. (1984), „Triangulace jednoduchých polygonů a ekvivalentní problémy“, Transakce ACM v grafice, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN  0730-0301, S2CID  33344266
  5. ^ Úvod do algoritmů, 2. vyd., T. H. Cormen, C. E. Leiserson, R. Rivest, a C. Stein, MIT Stiskněte, 2001. Úloha 15-1, s. 364.
  6. ^ Liu, Robin (1988), „O rozkladu polygonů na rovnoměrně monotónní části“, Dopisy o zpracování informací, 27 (2): 85–89, doi:10.1016 / 0020-0190 (88) 90097-X.
  7. ^ A b Toussaint, G. T.; El Gindy, H. A. (1984), „Separation of two monotone polygons in linear time“, Robotica, 2 (4): 215–220, doi:10.1017 / S0263574700008924.
  8. ^ A b Bose, Prosenjit; van Kreveld, Marc (2005), „Zobecnění monotónnosti: Rozpoznávání speciálních tříd polygonů a mnohostěnů výpočtem pěkných zatáček“, International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142 / S0218195905001877, hdl:1874/24150.