Name
Abstract | ||
|---|---|---|
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 Z^2 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(n^2) is given to find inscribed squares in simple digital curves. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.10.004 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Jordan Curve Theorem,non-degenerate square,Inscribed Square Conjecture,infinite family,digital simple,Digital topology,digital plane,Simple closed digital curves,simple digital curve,8-connectivity,digital topology,n inscribed square,discrete version,related problem,single non-degenerate inscribed square,4-connectivity,inscribed square,integer vertex | Journal | 412 |
Issue | ISSN | Citations |
15 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Feliu Sagols | 1 | 4 | 1.58 |
| Raúl Marín | 2 | 1 | 0.82 |