Intersection points of planar curves can be computed

Abstract

Consider two paths $\mathit{\varphi }\mathrm{,}\mathit{\psi }:[0;1]\to {[0;1]}^2$ in the unit square such that $\mathit{\varphi }\mathrm{(}0\mathrm{)}=\mathrm{(}0\mathrm{,}0\mathrm{)}$ , $\mathit{\varphi }\mathrm{(}1\mathrm{)}=\mathrm{(}1\mathrm{,}1\mathrm{)}$ , $\mathit{\psi }\mathrm{(}0\mathrm{)}=\mathrm{(}0\mathrm{,}1\mathrm{)}$ and $\mathit{\psi }\mathrm{(}1\mathrm{)}=\mathrm{(}1\mathrm{,}0\mathrm{)}$ . By continuity of ϕ and ψ there is a point of intersection. We prove that from ϕ and ψ we can compute closed intervals ${\mathit{S}}_{\mathit{\varphi }}\mathrm{,}{\mathit{S}}_{\mathit{\psi }}\subseteq [0;1]$ such that $\mathit{\varphi }\mathrm{(}{\mathit{S}}_{\mathit{\varphi }}\mathrm{)}=\mathit{\psi }\mathrm{(}{\mathit{S}}_{\mathit{\psi }}\mathrm{)}$ .