Preprosti mnogokotnik

Preprôsti mnogokótnik je v ravninski geometriji mnogokotnik, katerega stranice se ne sekajo, in so paroma povezane, tako da tvorijo sklenjeno pot. Če se stranice sekajo, mnogokotnik ni preprost. Po navadi se pridevniška beseda »preprost« opušča in se z zgornjo definicijo definira mnogokotnik v splošnem.

Zgornja definicija zagotavlja naslednje značilnosti:

mnogokotnik obdaja območje (njegovo notranjost), ki ima vedno merljivo ploščino.
daljice, ki tvorijo mnogokotnik (imenovane stranice) se stikajo v svojih krajiščih, imenovanih oglišča ali manj formalno »koti«.
v vsakem oglišču se stikata točno dve stranici.
število stranic je vedno enako številu oglišč.

Dve stranici, ki se stikata v oglišču, po navadi morata tvoriti kot, ki ni iztegnjen (180°); drugače kolinearni daljici veljata za del ene stranice. Obstajajo sicer na primer zgledi konkavnih enakostraničnih petkotnikov pri katerih to velja, in so podobni petkotnikom degeneriranim v štirikotnike.

Matematiki običajno rabijo izraz »mnogokotnik« za objekt, ki ga tvorijo daljice, ne pa tudi za njegovo notranjost. Nekateri rabijo izraz »mnogokotnik« za ravninski lik (ali obliko), ki ga omejuje sklenjena sklenjena pot, sestavljena iz končnega zaporedja daljic, oziroma sklenjene lomnice. Glede na definicijo je ta meja lahko del samega mnogokotnika ali pa ne.^[1]

Preprosti mnogokotnik se imenuje tudi Jordanov mnogokotnik, ker se z Jordanovim krivuljnim izrekom lahko dokaže, da takšen mnogokotnik razdeli ravnino na dve območji, območje znotraj in območje zunaj mnogokotnika. Preprosti mnogokotnik je topološko enakovreden krožnici, njegova notranjost pa krogu.

Šibko preprosti mnogokotnik uredi

Če zaprta lomnica vložena v ravnino deli to ravnino na dve območji, od katerih je eno topološko enakovredno krogu, se takšna lomnica imenuje šibko preprosti mnogokotnik.^[2]^:177 Šibko preprosti mnogokotnik je neformalno mnogokotnik pri katerem se lahko stranice »stikajo«, ne morejo pa se »sekati«.

Na levi sliki je ABCDEFGHJKLM šibko preprosti mnogokotnik kjer modra barva označuje njegovo notranjost.

Po splošnejši definiciji šibko preprostih mnogokotnikov so limite zaporedij preprostih mnogokotnikov enake kombinatorične vrste s konvergenco pod Hausdorffovo metriko. »Notranjost« je lahko prazna. Lomnica ABCBA na zgornji sliki je šibko preprosti mnogokotnik - lahko se jo obravnava kot limito stisnjenja mnogokotnika ABCFGHA.

Nepreprosti šibko preprosti mnogokotniki se pojavljajo v računalniški grafiki in računalniško podprtem načrtovanju kot računalniška predstavitev mnogokotniških območij z luknjami: za vsako luknjo se tvori »rez«, ki jo poveže z zunanjo mejo. Glede na zgornjo sliko je ABCM zunanja meja ravninskega območja z luknjo FGHJ. Rez ED povezuje luknjo z zunanjostjo in se v izhajajoči predstavitvi šibko preprostega mnogokotnika prečka dvakrat.

Računalniški problemi uredi

V računalniški geometriji več pomembnih računalniških nalog obsega vhodne podatke v obliki preprostih mnogokotnikov. V vsakem od teh problemov je pri njegovi definiciji razločevanje med notranjostjo in zunanjostjo odločilno.^[3]

problem točke v mnogokotniku za dani preprosti mnogokotnik P in točko q išče ali q leži v notranjosti P.
za računanje ploščine mnogokotnikov je znanih več preprostih formul.
triangulacija mnogokotnika je delitev preprostega mnogokotnika v trikotnike. Čeprav se lahko konveksni mnogokotniki enostavno triangulirajo, je triangualacija splošnega preprostega mnogokotnika težje, ker se je treba izogibati stranicam, ki sekajo zunanjost mnogokotnika. Bernard Chazelle je leta 1991 pokazal, da se lahko vsak preprosti mnogokotnik z n oglišči triangulira z linearno časovno zahtevnostjo Θ(n), kar je optimalno. Enak algoritem se lahko uporabi pri določevanju ali sklenjena lomnica tvori preprosti mnogokotnik.
unija mnogokotnika je iskanje preprostega mnogokotnika ali mnogokotnikov, ki vsebujejo območje znotraj enega ali drugega preprostega mnogokotnika.
presek mnogokotnika je iskanje preprostega mnogokotnika ali mnogokotnikov, ki vsebujejo območje znotraj obeh preprostih mnogokotnikov.
konveksna ogrinjača preprostega mnogokotnika se lahko izračuna učinkoviteje kot konveksna ogrinjača drugih vrst vhodnih podatkov, kot je na primer konveksna ogrinjača množice točk.
Voronojev diagram preprostega mnogokotnika.
srednja os/topološki skelet/premočrtni skelet preprostega mnogokotnika.
premaknjena krivulja preprostega mnogokotnika.
spreminjanje velikosti mnogokotnika.
vsota Minkowskega preprostega mnogokotnika