Problem 46565. Find an inscribed square on a closed curve

Created by Ned Gulley

Solve Later

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.

Solve

Solution Stats

39 Solutions
5 Solvers

Last Solution submitted on Nov 04, 2024

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older 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.

ChrisR on 3 Nov 2024 at 15:13

Where is the square in the last test? The test passes with [1 3 5 7], but that's a rhombus. The angle test works because the dot products are 3, 3, -3, -3, and their sum is still zero. Perhaps checking that all dot products are zero (or less than a tolerance) would work.

Dyuman Joshi on 4 Nov 2024 at 15:20

Hello Chris, there is actually a typo from my side in the last test case.
Point #6 is supposed to be (1,-1) instead of (-1, 1) (which occurs twice).

I am unable to correct the test suite at this moment, I will update it inline with your feedback, as soon as I can.

Dyuman Joshi on 14 Nov 2024 at 17:48

Hello Chris, I have corrected the test case #7 and modified the test suite as per your suggestion.

Also, I have rescored the solutions.
It was interesting to see that quite a many solutions failed the last test case, incorrectly giving the rhombus as the solution
(i.e [1 3 5 7]).

Solution Comments

Show comments

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 46565. Find an inscribed square on a closed curve

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 46565. Find an inscribed square on a closed curve

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players