全部 标题 作者 关键词 摘要
Keywords: Shortest path,convex polyhedron,computing geometry,geodesics,Voronoi graph最短路,凸多面体,计算几何,测地线,Voronoi图.
Full-Text Cite this paper Add to My Lib
在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n2)（n为凸多面体的顶点数）.文章主要研究了k=2情形下的最短路问题,提出一个在O(n2)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n3
Full-Text
Contact Us
service@oalib.com
QQ:3279437679
WhatsApp +8615387084133
