### Micha Sharir: Eliminating depth cycles and its relatives

Sharir Micha#### BBC+G Seminar

on 10/16/20

For a finite set $A\subset \R^2$, a map $\varphi: A \to \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 \N$ and for every $\eps>0$ there is $N=N(n,\eps)\in \N$ such that the following holds. Assume that $\varphi :G(N)\to \R^2$ is an orientation preserving map where $G(N)$ is the grid $\{(i,j)\in \Z: -N \le i,j\le N\}$. Then there is an affine transformation $\psi :\R^2 \to \R^2$ and $z_0 \in \Z$ such that $z_0+G(n)\subset G(N)$ and $\|\varphi (z)-\psi(z)\|<\eps$ for every $z \in z_0+G(n)$. This result was previously proved in a completely different way by Ne\v set\v ril and Valtr, without obtaining any bound on $N$. Our proof gives $N(n,\eps)=O(n^4\eps^{-2})$. Joint work with Attila Por and Pavel Valtr.