Abstrakt. Vi introducerar begreppet en stjärna veckling av ytan P av en tredimensionell konvex polytop med n hörn, och använda den för att lösa flera problem relaterade till kortaste vägar på P. Den första algoritmen beräknar eggsekvenser som korsas av kortaste vägar på P i tid O(n 6 β(n) log n), där β(n) är en extremt långsamt växande funktion. En mycket enklare O(n 6 ) tid algoritm som hittar en liten superuppsättning av alla sådana eggsekvenser är också skissad. Den andra algoritmen är en O(n 8 log n) tidsprocedur för att beräkna den geodesiska diametern av P: den maximala möjliga separationen av två punkter på P med avståndet mätt längs P. Slutligen beskriver vi en algoritm som preprocessar P till en datastruktur som effektivt kan svara på frågorna i följande form: "Ges två punkter, vad är längden på den kortaste vägen ansluter dem?" Med tanke på en parameter 1 ≤ m ≤ n 2, kan den prebehandla P i tiden O(n 6 m 1 + π ), för alla δ > 0, till en datastruktur av storlek O(n 6 m 1 + δ ), så att en fråga kan besvaras i tid O ( ( ε n/m 1/4 ) log n). Om en frågepunkt alltid ligger på en kant av P, algoritmen kan förbättras för att använda O(n 5 m 1+δ ) förbehandlingstid och lagring och garantera O(n/m) 1/3 log n) frågetid för val av m mellan 1 och n.
Agarwal m.fl. REF lade fram en datastruktur av storlek O(n 6 m 1 +π ) som besvarar en tvåpunkts kortaste sökväg på en given konvex polytop i O(( ε n/m 1/4 ) log n) tid efter O(n 6 m 1 + π ) förbehandlingstid för varje fast 1 ≤ m ≤ n 2 och varje δ > 0.
Star unfolding of a polytope with applications
{'venue': 'SIAM J. Comput', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}