Wikipedia:Reference desk/Archives/Mathematics/2018 December 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 2

How many points to make the polygon ambiguous?

In 2-dimensional Euclidean space, how many points must be in a set, for it to be the set of vertices of each of two distinct non-self-intersecting polygons? NeonMerlin 06:04, 2 December 2018 (UTC)

The wording is a bit ambiguous here. One interpretation is, what is the smallest set that is the set of vertices of two different non-self-intersecting polygons? The answer to this is four points with one point inside the triangle formed by the other three. This is the set of vertices of three different quadrilaterals, which is fairly easy to see. A second interpretation is, what is the smallest n so that all sets with at least n elements are the set of vertices of two different non-self-intersecting polygons? The answer to this is that there is no such n; in fact the set of vertices of a convex polygon is not the set of vertices of any other non-self-intersecting polygon. To see this, let A₁, A₂, ... A_n be the vertices of a convex polygon C taken in order, and suppose that there a different non-self-intersecting polygon D on the same set. This other polygon D must contain a diagonal of C in order for it to be different. In other words there are k, l, with 1≤k<l≤n, 1<l-k<n-1, so that A_kA_l is an edge of D. The line A_kA_l divides the remaining points into non-empty sets {A_k+1, ..., A_l-1} = P and {A_l+1, ... A_n, A₁, ... A_k-1} = Q. I claim that D must have an edge connecting a point in P to a point in Q. Assume not and let A_rA_k be the other edge of D that contains A_k. The point A_r must be in either P or Q, but whichever set it's in the remaining vertices of D must be in the same set if there are no edges from P to Q. This is a contradiction, so there are A_m and A_n, with A_mA_n an edge of D, which are on opposite sides of the line A_kA_l. Let the segment A_mA_n intersect the line A_k and A_l at B. If B is within the segment A_kA_l then D is self-intersecting, a contradiction. If A_l is between B and A_k then A_l is inside the triangle A_mA_nA_k and C is not convex, a contradiction. Similarly, if A_k is between B and A_l then A_k is inside the triangle A_mA_nA_l and C is not convex, a contradiction. But these are the only possibilities for B so the initial assumption, that D exists, is false. --RDBury (talk) 11:05, 2 December 2018 (UTC)

@NeonMerlin: Four is enough. Draw a triangle and mark a fourth point inside. You can choose any of the three sides to be removed and replaced with two new sides, thus the same 4-point set serves as vertices of three different polygons, none of which is self-intersecting.

If you want to have two polygons at the same time, you'll need 6 points. Six is enough:

           A---B   E             A   B---E
           |  /   /|             |\   \  |
           | /   / |             | \   \ |
           |/   /  |             |  \   \|
           C   D---F             C---D   F

and you can't have fewer than that, as you need at least 3 per polygon. --CiaPan (talk) 12:37, 4 December 2018 (UTC)

The above holds for my silent assumption 'non-intersecting' means 'having no point in common'. However, if you relax it to 'have no interior point in common', then 4 is enough:

           A---B             A---B
           |  /|             |\  |
           | / |             | \ |
           |/  |             |  \|
           C---D             C---D

--CiaPan (talk) 12:44, 4 December 2018 (UTC)