Proximity and Motion Planning on 1_1-embeddable Tilings
Proximity and Motion Planning on 1_1-embeddable Tilings
复制标题
1_1-嵌入式平铺上的邻近和运动规划
DOI：
10.1109/isvd.2011.28
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Hiroshi Imai
中科院分区：
文献类型：
--
作者：
Norie Fu;Akihiro Hashikura;Hiroshi Imai
A motion planning problem on plane crystallographic graphs turned out to be important in nanotechnology due to recent innovation in techniques of handling real atoms on a physical lattice. The motion planning problem on graphs are well studied and it was shown that fast algorithms for proximity problems on graphs lead to fast motion planning algorithms. On the other hand, tilings are well studied as a model for plane crystallographic graphs and l1-embeddable tilings are enumerated by Deza, Grishukhin and Shtogrin. In this paper, we focus on the geometry of tilings and propose two proximity algorithms on l1-embeddable tilings for the application to nanotechnology. We show that Voronoi diagrams on tilings embeddable in the 3-dimensional l1lattice can be implicitly describes by Voronoi diagrams on the plane under appropriate convex piecewise linear functions with extra elaborations. We also propose a fast algorithm for another proximity problem, which we call nearest pair problem, on l1-embeddable tilings. Using these algorithms, we propose algorithms for the motion planning problem on l1-embeddable tilings.
