Results 1 to 4 of 4

Thread: Proof verification: Smallest Perimeter convex polygon

  1. #1
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    50
    Thanks
    1

    Proof verification: Smallest Perimeter convex polygon

    I have formulated a proof but was wondering if someone could verify that it is correct.

    Show that the smallest perimeter polygon containing a set of points is convex.


    A concave polygon is clearly not the shortest perimeter polygon that
    can be formed from a set of points. This can be seen by noting that if there are two line segments that form a reflex angle, then the there exists a shorter path between the end points of the two line segments. This intuition can be used in our proof.


    Assume $P$ is the smallest perimeter polygon of a set of points and that $P$ is non-convex (concave). If $P$ is concave this implies there is at least one reflex angle formed between two line segments. Suppose $\overline{PQ},\overline{QR}$ form a reflex angle. Now imagine we add a line segment $\overline{PR}$ to $P$ giving us triangle $PQR$. By the triangle inequality we know that $Length(\overline{PR}) < Length(\overline{PQ} + \overline{QR})$ which implies that there exists a shorter way to get between $P$ and $R$ then in our origianl polygon, which contradicts the assumption that $P$ is the smallest perimeter polygon. This means that $P$ must be convex.
    Attached Thumbnails Attached Thumbnails Proof verification: Smallest Perimeter convex polygon-4311ddfe-530c-471b-94dd-20ce90bdb0eb.jpeg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,879
    Thanks
    2888
    Awards
    1

    Re: Proof verification: Smallest Perimeter convex polygon

    Quote Originally Posted by mdm508 View Post
    Show that the smallest perimeter polygon containing a set of points is convex.
    This is an totally non-sense question. Do you even know what a polygon is?
    What set of points are you dealing with? It must be co-planar points. But then are you considering the polygon to be its boundary union its interior? OR WHAT?

    In other words, it appears that you have no idea of the definitions of that you are using.
    What if the set is a collection of colinear points? What polygon makes any sense to say contains that set?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    50
    Thanks
    1

    Re: Proof verification: Smallest Perimeter convex polygon

    I just copy and pasted the question from book. I know what a polygon is. Just assume that no points in the set are collinear. Assume it is just some set of points. Basically we are trying to show that the smallest perimeter polygon of a set of points is the Convex Hull.
    Last edited by mdm508; Jan 17th 2018 at 06:28 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,879
    Thanks
    2888
    Awards
    1

    Re: Proof verification: Smallest Perimeter convex polygon

    Quote Originally Posted by mdm508 View Post
    I just copy and pasted the question from book. I know what a polygon is. Just assume that no points in the set are collinear. Assume it is just some set of points. Basically we are trying to show that the smallest perimeter polygon of a set of points is the Convex Hull.
    Let this be a lesson: always give us ALL the information.
    You should have access to a mathematics library. This problem is discussed on page 75 of Roberts&Varberg. Read their explanation. then if you have questions, post them.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximum perimeter of n-sided polygon
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 29th 2015, 05:31 AM
  2. Replies: 4
    Last Post: May 8th 2015, 09:03 AM
  3. perimeter / area verification problem
    Posted in the Geometry Forum
    Replies: 2
    Last Post: Jan 5th 2010, 03:05 AM
  4. Exterior angles of a convex polygon HELP?
    Posted in the Geometry Forum
    Replies: 3
    Last Post: Sep 3rd 2009, 03:21 AM
  5. [SOLVED] Convex Polygon Proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Jan 25th 2008, 02:09 PM

/mathhelpforum @mathhelpforum