Problem 46565. Find an inscribed square on a closed curve
Here's an unproven conjecture from geometry: Every simple closed curve in a plane contains all four vertices of some square.
It's kind of remarkable. As far as we can tell right now, you can put at least one square on every single closed curve. Inspired by this, I made a simple discrete Cody-fied version of the problem. (And by the way, I'm not claiming it's mathematically equivalent...)
Given a list of points in [x y] format, return four indices into that list that form a square.
xy = [ 29 13
41 7
53 16
58 48
80 41
78 85
46 80
7 46 ]
Then the answer would be the indices given in ix. These indices point to the rows that contain the four vertices of the square.
ix = [ 2 5 7 8 ]
You can return the indices in any order that honors the cycle around the square, and the answer is not necessarily unique. The test suite just verifies that what you return is indeed a square.
Solution Stats
Problem Comments
-
2 Comments
Rafael S.T. Vieira
on 1 Nov 2020
Your test suite just checks whether a quadrilateral has equal sides, but that's not enough to form a square: rhombuses also have equal sides. Therefore, the test suite should also check a solution's angles.
PS: A test case filled with rhombuses and a single square on the curve would be instructional too.
Dyuman Joshi
on 19 Sep 2022
Test suite has been updated to check for a solution's angles as well and a mixed test case with rhombus and square mixed has been added.
Solutions have been rescored as well.
Solution Comments
Show commentsProblem Recent Solvers9
Suggested Problems
-
291 Solvers
-
513 Solvers
-
4970 Solvers
-
477 Solvers
-
307 Solvers
More from this Author50
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!