Vi presenterar en approximation algoritm som, med tanke på en enkel, möjligen nonconvex polyhedron P med n hörn i R 3, och två punkter s och t på dess yta @P, konstruerar en väg på @P mellan s och t vars längd är högst 7 (1 + "), där är längden på den kortaste vägen mellan s och t på @P, och " > 0 är en godtyckligt liten positiv konstant. Algoritmen körs i O(n 5=3 log 5=3 n) tid. Vi presenterar också en något snabbare algoritm som körs i O(n 8=5 log 8=5 n) tid och returnerar en väg vars längd är högst 15 (1 + ").
Varadarajan och Agarwal REF presenterade två algoritmer för beräkning av en väg på nonconvex polyhedra, en kör i O(n 5/3 log 5/3 n) tid och en något snabbare en kör i O(n 8/5 log 8/5 n) tid.
Approximating Shortest Paths on a Nonconvex Polyhedron
{'venue': 'In Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}