Not signed in (Sign In)

Vanilla 1.1.9 is a product of Lussumo. More Information: Documentation, Community Support.

Is this question acceptable?: The straightest possible path embeddable in a path of polygons

Bottom of Page

1 to 5 of 5

  1.  
  1.  
    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.
    • CommentAuthorarex
    • CommentTimeJan 12th 2011
     

    The question does not ask for an algorithm.

  3.  
    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.
    • CommentAuthorarex
    • CommentTimeJan 12th 2011
     

    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.

    • CommentAuthorarex
    • CommentTimeJan 12th 2011
     

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

1 to 5 of 5

  1.  
Back to Discussions Top of Page