P R E S E K List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 18 (1990/1991) Številka 3 Strani 186-190 Boris Lavric: TRIANGULACIJE VECKOTNIKOV Ključne besede: matematika, geometrija. Elektronska verzija: http://www.presek.si/18/1036-Lavric-veckotnik.pdf © 1990 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo TRIANGULACIJE VEČKOTNIKOV Najprej na kratko opredelimo nekaj pojmov, ki jih bomo rabili v nadaljevanju. Naj bodo A\, A2.....An različne točke dane ravnine. Večkotnik z oglišči Aj, A2.....An je končen del ravnine, ograjen s sklenjeno črto, sestavljeno iz daljtc A\ A2, A2A3,An^\An, AnA\. Te daljice imenujemo stranice večkotnika in morajo ustrezati pogojema: a. Sosednji stranici, torej stranici s skupnim ogliščem, ne ležita na isti premici. b. Nesosednji stranici nimata skupnih točk. Če ima večkotnik n oglišč, mu rečemo /i-kotnik. sedemkotnik trikotnik ABC, ki ni Stirikotnik ABC D lika na levi in desni nista večkotnika Navedena definicija je nekoliko prilagojena potrebam tega sestavka. Tako definirani večkotnik se namreč v literaturi pogostoimenuje enostavni ravninski večkotnik. Stranice tvorijo rob večkotnika, ostale točke večkotnika pa njegovo notranjost. Večkotnik je konveksen ali izbočen, če so vsi njegovi notranji koti izbočeni, torej manjši od 180°. Triangulacija večkotnika A\Ai...An je tako razkosanje tega večkotnika na trikotnike z oglišči v točkah Ai, A2, An, pri katerem poljubna dva trikotnika bodisi nimata nobene skupne točke bodisi imata skupno le oglišče ali le stranico. Konveksni večkotnik trianguliramo zelo preprosto. Poljubno ¡zbrano oglišče zveiemo z vsemi ostalimi in konveksni večkotnik tako razdelimo na ustrezne trikotnike. 5 triangulacijo nekonveksnega večkotnika pa je več dela. triangulacija sedemkotmka razkosanje petkotnika - nr triangulacija Izberemo oglišče takega večkotnika, ob katerem je notranji kot večji od 180° (glej definicijo), in ga označimo z A. Poglejmo iz A v notranjost večkotnika proti njegovemu robu. Opazimo vsaj eno oglišče, saj bi v nasprotnem primeru iz A videli le eno stranico, kar pa ni mogoče. Z diagonalo, ki veže A s tem ogliščem, razdelimo večkotnik na dva večkotnika z manjšim številom stranic. Na podoben način se nato lotimo teh dveh večkotnikov in nadaljujemo z razkosavanjem, dokler ne pridemo do triangulacije. Primer trianguliranja osemkotnika je prikazan na naslednji risbi prvi korak trianguliranja ena od (dveh mofnih) triangulacij Večkotnik ima lahko več triangulacij, vse pa imajo enako trikotnikov. Velja namreč tale rezultat. IZREK 1 .Vsaka triangulacija n-kotnika ima natanko n-2 trikotnikov. Dokaz bo s pomočjo matematične indukcije zelo kratek. Za trikotnik ni kaj dokazovati. Predpostavimo, da pri danem n > 3 izrek velja za vsak ic-kotnik, kjer je k < n. Ena od stranic poljubnega trikotnika iz triangulacije n-kotnika je njegova diagonala, ki ga razdeli na p-kotnik in g-kotnik. Pri tem seveda velja 3 < p < n, 3 3, obstajata vsaj dva trikotnika, ki imata dve stranici na njegovem robu. Pojem triangulacije lahko posplošimo na naslednji način. Naj bo .M končna podmnožica točk danega n-kotnika in naj vsebuje vsa njegova oglišča Ai, Aj.....An. Triangulacija z oglišči v A4 je tako razkosanje večkotnika Ai Ai.. ,An na trikotnike z og!i5či v .Vi, da je vsaka točka množice .M oglišče vseh tistih trikotnikov iz razkosanja, ki to točko vsebujejo. če množice .M ne navedemo, imenujemo pravkar definirano triangulacijo posplošena triangulacija večkotnika AjAi... A n, Oglejmo si zdaj enega od načinov, ki privede do triangulacije z ogliiČi v j\4. Najprej triangutiramo večkotnik A\Ai An, kar že znamo storiti. Vsak dobljeni trikotnik Ima lahko točke iz M £e v svoji notranjosti in na stranicah, če katera leži znotraj trikotnika, jo povežemo z njegovimi oglišči z daljicami. Enako storimo v novem razkosanju in tako nadaljujemo, dokler gre. Znotraj dobljenih trikotnikov ni več točk iz M. Nastale trikotnike razkosamo takole: Vse točke na eni stranici trikotnika zvežemo z daljicami z nasproti ležečim ogliščem in po potrebi enako storimo daje naslednji izrek. IZREK 2.če ima množica M r točk na robu n-kotnika in k točk v njegovi notranjosti, je v poljubni triangulaciji z oglišči v M natanko r + 2k —2 trikotnikov. Pri tem je seveda r > rt. Dokaz. Naj ima triangulacija z oglišči v M m trikotnikov. Potem je vsota vseh njihovih notranjih kotov enaka ml80D, Enako vsoto dobimo, če seštejemo notranje kote n-kotnjka, polne kote ob točkah iz .M v notranjosti n-kotnika in iztegnjene kote ob ostalih točkah iz _A/f na robu večkotnika. Torej velja ml80° = (n-2):80° + £360° + (r - n)l80° od koder sledi iskana enakost m — r + 2k — 2. n ~ 12 | r = U m = 20 k = 4 1 Sklenimo prispevek z nalogami. 4. Poišči tako posplošeno triangulacijo trikotnika, da se v vsakem njenem vozliSČu stikajo Štiri daljice triangulacije. 5. Naj ima množica M r točk na robu danega n-kotnika in k točk v njegovi notranjosti. Koliko daljic, nastalih pri triangulaciji z ogliŠČi v M.t ne leži na robu n-kotnika? Pri tem štejemo samo daljice, ki imajo samo krajišča v M. 6. Označimo s p število takih trikotnikov iz triangulacije z oglišči v Mt ki imajo dve stranici na robu n-kotnika, n > 3, Potem je v tej triangulaciji natanko p-j- 2k — 2 trikotnikov, ki nimajo nobene stranice na robu n-kotnika, če k točk iz leži v notranjosti n-kotnika. Dokaži, Rešitve nalog bodo v P-4, Boris Lavrič