Orientation preserving maps of the square grid

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10439096" target="_blank" >RIV/00216208:11320/21:10439096 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.14" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2021.14</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2021.14" target="_blank" >10.4230/LIPIcs.SoCG.2021.14</a>

Result language
angličtina
Original language name
Orientation preserving maps of the square grid
Original language description
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).
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA21-32817S" target="_blank" >GA21-32817S: Algorithmic, structural and complexity aspects of geometric configurations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-184-9
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Place of publication
Dagstuhl
Event location
Buffalo
Event date
Jun 7, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)