DocumentCode :
2828921
Title :
Proximity and Motion Planning on l_1-Embeddable Tilings
Author :
Fu, Norie ; Hashikura, Akihiro ; Imai, Hiroshi
Author_Institution :
Dept. of Comput. Sci., Univ. of Tokyo, Tokyo, Japan
fYear :
2011
fDate :
28-30 June 2011
Firstpage :
150
Lastpage :
159
Abstract :
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 l1 lattice 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.
Keywords :
computational geometry; crystallography; nanotechnology; path planning; Voronoi diagrams; convex piecewise linear functions; geometry; motion planning problem; nanotechnology; plane crystallographic graphs; proximity algorithms; tilings; Complexity theory; Crystals; Data structures; Lattices; Nearest neighbor searches; Orbits; Planning; Motion Planning; Proxmity; Tilings; Voronoi diagrams;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Voronoi Diagrams in Science and Engineering (ISVD), 2011 Eighth International Symposium on
Conference_Location :
Qingdao
Print_ISBN :
978-1-4577-1026-1
Electronic_ISBN :
978-0-7695-4483-0
Type :
conf
DOI :
10.1109/ISVD.2011.28
Filename :
5988930
Link To Document :
بازگشت