A geometry problem I worked on in a REU program from years ago just came to my mind.
Let's define a constant called "chord-arc constant" for any planar polygon as the largest ratio between 2 points' Euclidean distance and the shorter arc distance over all pairs of points on the polygon's edges. So essentially we are trying to find 2 points on a polygon's edges such that they are very close to each other on the plane, but the length of the edges connecting them is very long.
For example, for this polygon, if you pick the 2 red dots as your candidate pair of points, then the red solid line would be the arc distance between the points, and the red dotted line would be the Euclidean distance between them. And this particular candidate pair looks pretty close to achieving this polygon's "chord arc constant".
My questions are:
- Has this constant been formally defined/studied in any paper? If so, what's its formal name? ("chord-arc constant" is just a name that we made up)
- My gut feelings tell me that there doesn't exist a deterministic algorithm that can find any given polygon's chord-arc constant. As the number of edges increases, there are more and more possible candidate pairs, and any candidate pair, i.e., local optimum, can trap your algorithm there forever. Even if you managed to make your algorithm avoid being stuck around local optimums by giving it some random jumping behavior, you still can't find the exact pair of points, because even if you are in theory very very close to the global optimal solution, you can still almost always nudge either or both points to get a better result. And even if you think no more nudging is needed, you will never know that for certain. Is there a way to prove that a deterministic algorithm doesn't exist?