This paper investigates how graph representation can be created for the mesh which is a discrete approximation of n-dimensional continuous space. The paper discusses the relationship between mesh dimensionality and the type and quantity of edges connecting each vertex with its neighbors. Basing on the analysis, a simple algorithm is also proposed to create such graph representation. The purpose of the graph is to search optimal paths and trajectories in the represented space.
Tomasz Kosicki
. Graph representation of n-dimensional space[J]. Advances in Manufacturing, 2014
, 2(1)
: 54
-60
.
DOI: 10.1007/s40436-014-0065-2
1. LaValle SM, Jr Kuffner JJ (2001) Randomized kinodynamic
planning. Int J Robot Res 20(5):378–400
2. Applegate DL, Bixby RE, Chva´tal V et al (2011) The travelling
salesman problem: a computational study. Princeton University
Press, Princeton
3. Sa´nchez G, Latombe JC (2002) Using a PRM planner to compare
centralized and decoupled planning for multi-robot system. In:
IEEE international conference on robotics and automation, vol 2,
pp 2112–2119
4. Carpin S (2006) Randomized motion planning: a tutorial. Int J
Robot Autom 21(3):184–195
5. LaValle SM (2006) Planning algorithms. Cambridge University
Press, Cambridge
6. Sukharev AG (1971) Optimal strategies of the search for an
extremum. USSR Comput Math Math Phys 11(4):910–924
7. Gross JL, Yellen J (2003) Handbook of graph theory. CRC Press,
Boca Raton
8. Hogben L (2013) Handbook of linear algebra. 2nd edn. Chapman
and Hall/CRC, Boca Raton
9. Goodman JE, O’Rourke J (2004) Handbook of discrete and
computational geometry. 2nd edn. Chapman and Hall/CRC, Boca
Raton
10. Coxeter HSM (1973) Regular polytopes. 3rd edn. Dover Publications,
New York
11. Lee J (2013) Introduction to topological manifolds. 2nd edn.
Springer, New York
12. Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization
by a colony of cooperating agent. IEEE Trans Syst Man
Cybern 26(1):29–41
