Louis Theran

Louis Theran (University of St Andrews)

Unlabelled rigidity problems

Algebra and Geometry Seminar

15th November 2018, 9:00 am – 10:00 am
Howard House, 4th Floor Seminar Room

Let p= {p_1, ..., p_n} be a configuration of n points in d-dimensional Euclidean space and G a graph with n vertices {1, ..., n} and m edges. The pair (G,p) is said to be globally rigid if p is determined (up to an unknowable ambient isometry) by the m distance measurements |p_j - p_i| corresponding to the edges of G, along with the labelling information associating the pairwise distances to edges.

I’ll talk about a seemingly harder version of this problem where we have access to only the m pairwise distance measurements as an unordered set, and the number of vertices n of G. Under the hypothesis that p is generic, we can recover G and p from these unlabelled distance measurements if and only if (G,p) was globally rigid. This generalises to any “generically globally rigid” graph a result of Boutin and Kemper which dealt with the complete graph.

Time permitting, I will also discuss the case when the unlabelled measurements arise from linear combinations of pairwise distance measurements.

Joint work with Shlomo Gortler and Dylan Thurston; Ioannis Gkioulekas, Shlomo Gortler, and Todd Zickler

Comments are closed.