Orientation preserving maps of the n × n grid
Imre Bárány, Attila Pór, Pável Valtr · Journal of Computational Geometry (Carleton University) · 2022
For a finite set $A\subset \mathbb{R}^2$, a map $\varphi: A \to \mathbb{R}^2$ is orientation preserving if for every non-collinear triple $u,v,w \in A$ the orientation of the triangle $u,v,w$ is the same as that of the triangle $\varphi(u),\varphi(v),\varphi(w)$. We prove that for every $n \in \mathbb{N}$ and for every $\varepsilon>0$ there is $N=N(n,\varepsilon)\in \mathbb{N}$ such that the following holds. Assume that $\varphi :G(N)\to \mathbb{R}^2$ is an orientation preserving map where $G(N)$ is the grid $\{(i,j)\in \mathbb{Z}: -N \le i,j\le N\}$. Then there is an affine transformation $\psi :\mathbb{R}^2 \to \mathbb{R}^2$ and $z_0 \in \mathbb{Z}$ such that $z_0+G(n)\subset G(N)$ and $\|\psi \circ \varphi (z)-z\|<\varepsilon$ for every $z \in z_0+G(n)$. This result was previously proved in a completely different way by Nešetřil and Valtr, without obtaining any bound on $N$. Our proof gives $N(n,\varepsilon)=O(n^4\varepsilon^{-2})$.