%0 Journal Article
%T The Problem of Shortest Path in 3D Space<br>三维空间中的最短路问题
%A SHI Hai-hu
%A <br>施海虎
%J 软件学报
%D 1999
%I 
%X 在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n2)（n为凸多面体的顶点数）.文章主要研究了k=2情形下的最短路问题,提出一个在O(n2)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n3
%K Shortest path
%K convex polyhedron
%K computing geometry
%K geodesics
%K Voronoi graph<br>最短路
%K 凸多面体
%K 计算几何
%K 测地线
%K Voronoi图.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=34F4A6FA1763B811&yid=B914830F5B1D1078&vid=F3090AE9B60B7ED1&iid=DF92D298D3FF1E6E&sid=FAC9AF09A23B46DD&eid=583C993D4E08F5CE&journal_id=1000-9825&journal_name=软件学报&referenced_num=1&reference_num=8