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


Download (938kB) | Preview


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.

Item Type: Article
Additional Information: Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Mathematics, University College London, United Kingdom Department of Mathematics, Western Kentucky University, Bowling Green, KY, United States Department of Applied Mathematics, Charles University, Praha, Czech Republic Export Date: 20 February 2023 Funding details: 131529, 132696, 133819, 21-32817S Funding details: Grantová Agentura České Republiky, GA ČR Funding text 1: Acknowledgments. The work of I. Bárány was partially supported by Hungarian National Research Grants No 131529, 132696, and 133819. The work by P. Valtr was supported by the grant no. 21-32817S of the Czech Science Foundation (GAƒR). We thank three anonymous referees for carefully checking earlier versions of this paper and for pointing out several inaccuracies.
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA73 Geometry / geometria
Depositing User: MTMT SWORD
Date Deposited: 22 Mar 2023 12:55
Last Modified: 22 Mar 2023 12:55

Actions (login required)

Edit Item Edit Item