Jump to content

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

From Wikipedia, the free encyclopedia
Mathematics desk
< December 1 << Nov | December | Jan >> Current desk >
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

[edit]

How many points to make the polygon ambiguous?

[edit]

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)[reply]

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 A1, A2, ... An 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 AkAl is an edge of D. The line AkAl divides the remaining points into non-empty sets {Ak+1, ..., Al-1} = P and {Al+1, ... An, A1, ... Ak-1} = Q. I claim that D must have an edge connecting a point in P to a point in Q. Assume not and let ArAk be the other edge of D that contains Ak. The point Ar 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 Am and An, with AmAn an edge of D, which are on opposite sides of the line AkAl. Let the segment AmAn intersect the line Ak and Al at B. If B is within the segment AkAl then D is self-intersecting, a contradiction. If Al is between B and Ak then Al is inside the triangle AmAnAk and C is not convex, a contradiction. Similarly, if Ak is between B and Al then Ak is inside the triangle AmAnAl 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)[reply]
@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)[reply]
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)[reply]