Publication at Faculty of Mathematics and Physics |
2021
Abstract
For a finite set A in ℝ^2, a map φ : A -> ℝ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 φ(u), φ(v), φ(w). We prove that for every n and for every ε > 0 there is N = N(n, ε) such that the following holds.
Assume that φ : G(N) -> ℝ2 is an orientation preserving map where G(N) is the grid {(i, j) in ℤ^2 : -N <= i, j <= N}. Then there is an affine transformation ψ : ℝ^2 to ℝ^2 and a in ℤ^2 such that a + G(n) is a subset of G(N) and ||ψ ° φ(z) - z|| < ε for every z in a + 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, ε) = O(n^4*ε-2).