Geometrical Treatment of Periodic Graphs with Coordinate System Using Axis-fiber and an Application to a Motion Planning

Motivated by an application to nanotechnology, Voronoi diagrams on (ℓ₁-embeddable) periodic graphs and a motion planning problem on those graphs have been investigated by Fu, Hashikura, Imai and Moriyama. In this paper, through the investigations on the coordinate system using geodesic fibers defined originally as invariants on periodic graphs by Eon, we show that a fast geometric algorithm for the motion planning problem is possible on periodic graphs with nice properties.