Abstrakt
We prove that the regular square grid of points in the integer lattice cannot be recovered from an arbitrary n^2-element subset of Z^2 via a mapping with prescribed Lipschitz constant (independent of n). This answers negatively a question of Feige from 2002.
Our resolution of Feige's question takes place largely in a continuous setting and is based on some new results for Lipschitz mappings falling into two broad areas of interest, which we study independently. Firstly the present work contains a detailed investigation of Lipschitz regular mappings on Euclidean spaces, with emphasis on their bilipschitz decomposability in a sense comparable to that of the well known result of Jones.
Secondly, we build on work of Burago and Kleiner and McMullen on non-realisable densities. We verify the existence, and further prevalence, of strongly non-realisable densities inside spaces of continuous functions.