Abstrakt. Vi anser online routing algoritmer för routing mellan hörnen av inbäddade planar straight linje grafer. Våra resultat inkluderar (1) två deterministiska minneslösa routingalgoritmer, en som fungerar för alla Delaunay triangulationer och den andra som fungerar för alla vanliga trianguleringar, (2) en randomiserad minneslös algoritm som fungerar för alla trianguleringar, (3) en O(1) minnesalgoritm som fungerar för alla konvexa underavdelningar, (4) en O(1) minnesalgoritm som approximerar den kortaste vägen i Delaunay triangulationer, och (5) teoretiska och experimentella resultat på konkurrenskraften hos dessa algoritmer. Nyckelord. Routing, Online algoritmer, Delaunay trianguleringar, kortaste vägen, spänner över väg 1. Inledning. Att finna vägar, eller routing, är centralt för ett antal områden, inklusive geografiska informationssystem, stadsplanering, robotik och kommunikationsnät. I många fall är kunskap om den miljö där routing äger rum inte tillgänglig i förväg, och fordonet/roboten/packet måste lära sig denna information genom utforskning. Algoritmer för routing i dessa typer av miljöer kallas online [3] routingalgoritmer. I detta papper vi anser online routing i följande abstrakta inställning: Miljön är en planar rak linje graf [17], T, med n hörn, vars kanter viktas av Euclidean avstånd mellan sina endpoints, källan v src och destination v dst är hörn av T, och ett paket kan bara röra sig på kanter av T. Inledningsvis, ett paket bara vet v src, v dst, och N (v src ), där N (v ) betecknar den uppsättning hörn i anslutning till v. Vi klassificerar online routing algoritmer baserat på deras användning av minne och / eller randomisering. Definiera v cur som den vertex vid vilken paketet för närvarande lagras. En routing algoritm kallas minneslös om nästa steg som tas av ett paket beror endast på v cur, v dst, och N (v cur ). En algoritm randomiserades om nästa steg som tas av ett paket väljs slumpmässigt från N (v cur ). En randomiserad algoritm är minneslös om den distribution som används för att välja mellan N (v cur ) är en funktion endast v cur, v dst, och N (v cur ). Motiveringen för att studera minneskraven för routingalgoritmer kommer från kommunikationsnät, där minne som används av en algoritm resulterar i huvudinformation som färdas med ett paket. Eftersom denna information endast används för routing och inte är till någon nytta för avsändaren eller mottagaren, producerar den effektivt en minskning av kommunikationsbandbredden. För en algoritm A säger vi att en graf besegrar A om det finns en källa/destination par så att ett paket aldrig når destinationen när den börjar vid källan. Om A hittar en väg P från v src till v dst kallar vi P A vägen från v src till v dst. Här använder vi termen väg i intuitiv betydelse snarare än en strikt graf teoretisk känsla, eftersom P kan besöka samma vertex mer än en gång. I detta dokument betraktar vi också, som ett specialfall, en klass av "väluppfostrade" trianguleringar. Voronoi diagram [16] av S är en uppdelning av utrymme i celler så att alla punkter i en Voronoi cell är närmare samma element p  på S än någon annan punkt i S. Delaunay triangulation är den raka-line ansikte dubbla av
Senare övervägde Bose och Morin REF olika metoder för ansiktsdragning i trianguleringen och i synnerhet i Delaunay-trianguleringen.
Online Routing in Triangulations
{'venue': 'in Proc. of the 10 th Annual Int. Symp. on Algorithms and Computation ISAAC', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}