Orientation Preserving Maps of the Square Grid

Bárány, Imre and Pór, Attila and Valtr, Pavel (2022) Orientation Preserving Maps of the Square Grid. JOURNAL OF COMPUTATIONAL GEOMETRY, 13 (2). pp. 73-89. ISSN 1920-180X

Preview

Text 10.4230_lipics.socg.2021.14.pdf Download (938kB) | Preview

Abstract

For a finite set A ⊂ R2, a map φ: A → R2 is orientation preserving if for every non-collinear triple u, v, w ∈ 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 ∈ N and for every ε > 0 there is N = N(n, ε) ∈ N such that the following holds. Assume that φ: G(N) → R2 is an orientation preserving map where G(N) is the grid {(i, j) ∈ Z2: −N ≤ i, j ≤ N}. Then there is an affine transformation ψ: R2 → R2 and z0 ∈ Z2 such that z0 + G(n) ⊂ G(N) and ∥ψ ◦ φ(z) − z∥ < ε for every z ∈ z0 + 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(n4ε−2). © 2022, Carleton University. All rights reserved.

Actions (login required)

Edit Item