A finite set of points in a plane have a certain property:
If we consider any 3 points in the set, and the triangle generated by these points, then NONE of the other points in the set is in the interior of this triangle.
Does it follow that we can form a convex polygon having all points as vertices?
Asked
Active
Viewed 105 times
3
-
3Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please [edit] the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Apr 02 '21 at 05:08
-
What it you take three points on a line? – copper.hat Apr 02 '21 at 21:53
2 Answers
2
The answer is No because of "degenerate cases": Take three points forming an equilateral triangle and a fourth point in the interior of one of the edges.
If you exclude such things, using a more careful formulation of the problem, the answer is Yes, because of Carathéodory's theorem. This theorem says that any point in the convex hull of a given set $S\subset{\mathbb R}^2$ is in the convex hull of three points of $S$.
Let $M$ be the set of given points. The convex hull of this set is a convex polygon $P$ with vertex set $S\subset M$, and is then also the convex hull of $S$. When $S$ is not all of $M$ then there is a $p\in M$ which lies in the interior of $P$. This point $p$ would then lie in a triangle formed by points of $S\subset M$, but your clause has forbidden that.
Christian Blatter
- 226,825
-
A point of clarification, Professor: isn't the "interior of a triangle" defined as the set of all points in the convex hull of the triangle's vertices? If so, it seems to me that the OP's problem statement (which, I'll grant you, isn't sharply clear) would actually exclude such cases as the one you're offering as a counter-example. I'm sorry, I'm probably missing something obvious, but I have to ask. – user3733558 Apr 02 '21 at 14:39
-
1@user3733558: I'd say the "interior of a triangle" is the actual interior, containing no boundary points. – Christian Blatter Apr 02 '21 at 14:49
-
I suspect OP's definition matches this one. But I thought exactly as you do at first as well. Clearly, the OP should improve the problem statement and clarify that point. Thanks for your time, Professor. – user3733558 Apr 02 '21 at 14:53
-
An even more basic reason why the answer is "no": the set could be empty. – Especially Lime Apr 11 '21 at 15:45
0
No.
Consider a five-sided polygon: a square with an extra vertex on one side, slightly inwards. This is a concave polygon, but fulfills the stated criteria: pick any three vertices, and the triangle formed contains none of the other vertices.
Glärbo
- 26
-
2I don't think your counter-example works. Take top-left, top-right and bottom-left. You haven't drawn that triangle, and it contains one of the vertices (top-middle). – user3733558 Apr 02 '21 at 12:07
-