Skip to Main content Skip to Navigation
Journal articles

An application-based characterization of dynamical distance geometry problems

Abstract : The dynamical Distance Geometry Problem (dynDGP) is the problem of finding a realization in a Euclidean space of a weighted undirected graph G representing an animation by relative distances, so that the distances between realized vertices are as close as possible to the edge weights. In the dynDGP, the vertex set of the graph G is the set product of V , representing certain objects, and T , representing time as a sequence of discrete steps. We suppose moreover that distance information is given together with the priority of every distance value. The dynDGP is a special class of the DGP where the dynamics of the problem comes to play an important role. In this work, we propose an application-based characterization of dynDGP instances, where the main criteria are the presence or absence of a skeletal structure, and the rigidity of such a skeletal structure. Examples of considered applications include: multi-robot coordination, crowd simulations, and human motion retargeting.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download
Contributor : Antonio Mucherino <>
Submitted on : Tuesday, September 25, 2018 - 11:25:30 AM
Last modification on : Wednesday, October 14, 2020 - 4:07:00 AM
Long-term archiving on: : Wednesday, December 26, 2018 - 4:51:55 PM


dynDGP-applications (1).pdf
Files produced by the author(s)



Antonio Mucherino, Jérémy Omer, Ludovic Hoyet, Paolo Robuffo Giordano, Franck Multon. An application-based characterization of dynamical distance geometry problems. Optimization Letters, Springer Verlag, 2020, 14 (2), pp.493-507. ⟨10.1007/s11590-018-1302-6⟩. ⟨hal-01846265⟩



Record views


Files downloads