Vi undersöker de beräkningsproblem som är förknippade med kombinatoriska ytor. Specifikt, Vi presenterar en algoritm (baserad på Brahana-Dehn-Heegaazd metod) för att omvandla polygonal schema av en stängd triangulerad yta till dess kanoniska form i O (n log n) tid, där n är det totala antalet hörn, kanter och ansikten. Vi ger också en O(n log n + gn) algoritm för att konstruera kanoniska generatorer av den grundläggande gruppen av en yta av släktet g. Detta är användbart för att konstruera homeomorfismer mellan kombinatoriska ytor. 1 Det största problemet i topologin av slutna ytor är sökandet efter topologiska invarianter av slutna ytor så att vi kan avgöra om två godtyckligt givna doserade ytor är eller inte är homeomorfa, se t.ex. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Det följer då, att det huvudsakliga beräkningsproblemet är att hitta effektiva metoder för att beräkna dessa invarianter och för två slutna homeomorphic ytor, att cotutruct homeomorphism.~ mellan dem. I den här artikeln presenterar vi sådana algoritmer. Vi antar att läsaren har någon famlliaritet med topologi av ytor (se t.ex., [2, 4] ). Det är välkänt att en sluten yta kan representeras som en enkel polygon vars kanter är märkta med symboler, varje symbol inträffar exakt två gånger, och varje symbol ges ett tecken (:t=). Ytan erhålls * Med stöd av ESPRIT II:s grundläggande forskningsåtgärd E.C. Enligt kontrakt nr 3075 (projekt ALCOM). På permission från Courart ].n.stltute, New York University. Denna författare stöds också av den tyska vetenskapsstiftelsen Fonatlon (DFG) och NSF Grants #DCR-84-01898 och ~CCR-87-03458. Tillstånd att utan avgift kopiera hela eller delar av detta material beviljas under förutsättning att kopiorna inte görs eller distribueras för direkt kommersiell fördel, ACM-upphovsrättsmeddelandet och titeln på publikationen och dess datum visas, och meddelande ges om att kopiering sker genom tillstånd från Föreningen för datormaskiner. För att kopiera på annat sätt, eller för att återpublicera, krävs en avgift och/eller ett särskilt tillstånd. Genom att identifiera de kanter som motsvarar en symbol, där tecknen anger om identifieringen är med (lika kännetecken) eller utan (motstående tecken) en vridning. Se figur 1 för ett oktognalschema som motsvarar dubbel-torus. Omvänt, varje enkel polygon där varje kant är märkt med en godtyckligt signerad symbol och varje osignerad symbol visas exakt två gånger representerar en stängd yta. Vi kallar detta en polygonisk achema av ytan. Dessutom har varje homeomorfa ytklass en kanonisk form i det polygonala schemat. Det finns en klassisk algoritm för att omvandla ett polygonalt schema till dess kanoniska form. Algoritmen beror huvudsakligen på Brahana (se [1] ), även om klassificeringssatsen är från Dehn och Heegaard. Vi kallar det Brahana-DelmHeegaard (alfabetisk ordning) eller BDH algoritm. Det är inte uppenbart hur denna algoritm kan implementeras i o(n 2) tid, där n är det totala antalet hörn, kanter och ansikten. Vi kommer att presentera en algoritm som körs i tid O (nlog n). Vårt andra resultat visar att vi, med tanke på en triangulerad sluten yta, kan konstruera en "kanonisk" uppsättning generatorer för dess grundläggande grupp i tid O (nlogn + gn), där g är släktet av ytan. Med hjälp av detta kan vi skära upp ytan i en plan polygon så att dess gräns måste identifieras på ett visst kanoniskt sätt. 102 Försäkrings- och återförsäkringsföretag, försäkringsholdingföretag, försäkringsholdingföretag, försäkringsholdingföretag, försäkringsholdingföretag, försäkringsholdingföretag, försäkringsholdingföretag och försäkringsholdingföretag
Vegter och Yap REF visade att kanonisk schemata finns med total komplexitet O(ng) där g är ytan släktet; detta band är tight i värsta fall, och de visade också att ett kanonisk schema kan hittas i tid O(ng).
Computational complexity of combinatorial surfaces
{'venue': "SCG '90", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}