Two discrete versions of the Inscribed Square Conjecture and some related problems

The Inscribed Square Conjecture has been open since 1911. It states that any plane Jordan curve J contains four points on a non-degenerate square. In this article two different discrete versions of this conjecture are introduced and proved. The first version is in the field of digital topology: it is proved that the conjecture holds for digital simple closed 4-curves, and that it is false for 8-curves. The second one is in the topological graph theory field: it is proved that any cycle of the grid Z2 contains an inscribed square with integer vertices. The proofs are based on a theorem due to Pak. An infinite family of 4-curves in the digital plane containing a single non-degenerate inscribed square is introduced as well as a second infinite family containing one 4-curve with exactly n inscribed squares for each positive integer value of n. Finally an algorithm with time complexity O(n2) is given to find inscribed squares in simple digital curves.