tea.mathoverflow.net - Discussion Feed (The straightest possible path embeddable in a path of polygons)

arex comments on "The straightest possible path embeddable in a path of polygons" (12604)

2011-01-12T22:34:14-08:00

(Err, the path must of course remain within the polygon, which is closed -- that is, includes its boundary.)

arex comments on "The straightest possible path embeddable in a path of polygons" (12603)

2011-01-12T22:17:58-08:00

The question is in the following excerpt: "I suspect, or rather I'm hoping, that both curves, the one with the smallest segment count and the straightest one are identical. I'd appreciate help showing that is or isn't the case." Also, Bill Thurston asked in a comment, "Is it correct that you are asking whether there is a path that simultaneously minimizes the number of segments and also minimizes the sum of the absolute value of angles?", to which the reply was "yes".

You have indicated in a comment a solution in the case that the polygon is not simple. The question remains unanswered in the case that the polygon is simple. The original question made no indication of this assumption, but it appears to have been the intent. So the question may be treated as follows:

"Suppose a simple polygon is given, along with two points, s and t, within the polygon. Is there a polygonal path from s to t that simultaneously minimizes the number of segments and amount of turning. Simple means homeomorphic to a disk; a polygonal path is a piecewise-linear curve; and turning is measured by the sum of the absolute values of the turning angles."

I believe the question as I have written above is appropriate for MathOverflow. I would have gladly edited this into the question long ago, but I don't have enough reputation to do so.

Dmitri Pavlov comments on "The straightest possible path embeddable in a path of polygons" (12599)

2011-01-12T20:42:25-08:00

The question does ask for an algrorithm (“We seek to install the smallest number of light beam relays required to forward a signal as quickly as possible though the tunnel from source to the destination.”),
but the poster meant something else.

arex comments on "The straightest possible path embeddable in a path of polygons" (12573)

2011-01-12T16:32:15-08:00

The question does not ask for an algorithm.

Dmitri Pavlov comments on "The straightest possible path embeddable in a path of polygons" (12552)

2011-01-12T11:03:56-08:00

Is this question acceptable?
http://mathoverflow.net/questions/51826/the-straightest-possible-path-embeddable-in-a-path-of-polygons

This question can be solved by a straightforward application of an elementary technique
from an undegraduate-level course on computational geometry
combined with Dijkstra's algorithm (also undergraduate level).

Clearly, this is not a research-level question,
and, moreover, we now have a SE site devoted specifically to TCS.