Abstract
This paper proposes a dynamical notion of discrete geodesics, understood as straightest trajectories in discretized curved spacetime. The proposed notion is generic, as it is formulated in terms of a general deviation function, but readily specializes to metric spaces such as discretized pseudo-riemannian manifolds. It is effective: an algorithm for computing these geodesics naturally follows, which allows numerical validation—as shown by computing the perihelion shift of a Mercury-like planet. It is consistent, in the continuum limit, with the standard notion of timelike geodesics in a pseudo-riemannian manifold. Whether the algorithm fits within the framework of cellular automata is discussed at length.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arrighi, P., Dowek, G.: The physical Church-Turing thesis and the principles of quantum theory. Int. J. Found. of Comput. Sci. 23, 1131 (2012)
Arrighi, P., Dowek, G.: Discrete geodesics. arXiv Pre-print, with program available when downloading source (2015)
Arrighi, P., Facchini, S., Forets, M.: Quantum walks in curved spacetime (2015). Pre-print arXiv:1505.07023
Brewin, L.: Particle paths in a schwarzschild spacetime via the regge calculus. Class. Quantum Gravity 10(9), 1803 (1993)
Cianfrani, F., Montani, G.: Dirac equations in curved space-time vs. papapetrou spinning particles. EPL (Europhysics Letters) 84(3), 30008 (2008)
Di Molfetta, G., Brachet, M., Debbasch, F.: Quantum walks as massless dirac fermions in curved space-time. Phys. Rev. A 88(4), 042301 (2013)
Di Molfetta, G., Brachet, M., Debbasch, F.: Quantum walks in artificial electric and gravitational fields. Phys. A: Stat. Mech. Appl. 397, 157–168 (2014)
d’Inverno, R.: Introducing Einstein’s Relatvity. Oxford University Press, USA (1899)
Gandy, R.: Church’s thesis and principles for mechanisms. In: Barwise, J., Keisler, H.J., Kunen, K. (eds.) The Kleene Symposium. North-Holland Publishing Company, Amsterdam (1980)
Lorenzi, M., Ayache, N., Pennec, X.: Schilds ladder for the parallel transport of deformations in time series of images. In: Székely, G., Hahn, H.K. (eds.) Information Processing in Medical Imaging, pp. 463–474. Springer, Heidelberg (2011)
Marsden, J.E., West, M.: Discrete mechanics and variational integrators. Acta Numer. 2001 10, 357–514 (2001)
Martínez, D., Velho, L., Carvalho, P.C.: Computing geodesics on triangular meshes. Comput. Graph. 29(5), 667–675 (2005)
Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM J. Comput. 16(4), 647–668 (1987)
Peyré, G., Péchaud, M., Keriven, R., Cohen, L.D.: Geodesic methods in computer vision and graphics. Found. Trends Comput. Graph. Vis. 5(3–4), 197–397 (2010)
Polthier, K., Schmies, M.: Straightest geodesics on polyhedral surfaces. In: Discrete Differential Geometry: An Applied Introduction, SIGGRAPH 2006, p. 30 (2006)
Vincent, F.H., Gourgoulhon, E., Novak, J.: 3+1 geodesic equation and images in numerical spacetimes. Class. Quant. Gravity 29(24), 245005 (2012)
Williams, R.M., Ellis, G.F.R.: Regge calculus and observations. i. formalism and applications to radial motion and circular orbits. Gen. Relativ. Gravit. 13(4), 361–395 (1981)
Acknowledgements
This work has been funded by the ANR-12-BS02-007-01 TARMAC grant, the ANR-10-JCJC-0208 CausaQ grant, and the John Templeton Foundation, grant ID 15619. Pablo Arrighi benefited from a visitor status at the IXXI institute of Lyon.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Arrighi, P., Dowek, G. (2015). Discrete Geodesics and Cellular Automata. In: Dediu, AH., Magdalena, L., Martín-Vide, C. (eds) Theory and Practice of Natural Computing. TPNC 2015. Lecture Notes in Computer Science(), vol 9477. Springer, Cham. https://doi.org/10.1007/978-3-319-26841-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-26841-5_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26840-8
Online ISBN: 978-3-319-26841-5
eBook Packages: Computer ScienceComputer Science (R0)