Find a set of $n$ points such that any triangulation gives a vertex of degree $n-1$, i.e. the vertex is incident to $n-1$ edges. It is easy to do if we place $n-1$ points on a horizontal line and the remaining point above the line. My question is: are there more general set of points that can do? Especially points that are in general position: no 3 points on same line, no 4 points on same circle, etc.
Find a set of $n$ points such that any triangulation gives a vertex of degree $n-1$.
1 Answers
Yes, you can let $n-1$ points lie on a (non-circular) arc arching away from the $n$-th point so that if you connect the $n$-th point with any two of the others the resulting triangle contains all points between the two.
[Edit in response to comments:]
I see now that the term "arching away" wasn't precise enough. What we need is that the $n-1$ points lie on a (non-circular) arc that is everywhere concave as seen from the $n$-th point, that is, that the lines connecting the $n$-th point to the arc lie everywhere on the concave side of the arc and nowhere inside its convex hull. For instance, if the $n$-th point is $(0,0)$, the $n-1$ points could lie on the curve $y=\mathrm e^x$ to the left of the point $(1,\mathrm e^1)$. At that point, the line from $(0,0)$ to the curve is tangent to the curve; for points to the left, the line lies on the concave side of the curve, whereas for points to the right the line crosses the curve and ends on its convex side.
-
0In fact, it seems I don't even need the n-th point now. It seems among those $n-1$ points on the arc, there is a vertex whose degree is $n-2$. Am I right? – 2012-04-11
-
0@FiniteA: No. Those $n-1$ points form a convex $n-1$-gon, and you can triangulate that without one vertex having degree $n-2$ -- see for instance [this image](http://en.wikipedia.org/wiki/File:Catalan-Hexagons-example.svg). – 2012-04-11
-
0My mistake. One last thing: would this point set works? {(0,0),(k, e^k) : k = 1..n-1.} – 2012-04-11
-
0@FiniteA: In my previous comment I linked to an image showing triangulations of a convex $(n-1)$-gon without a vertex of degree $n-2$. You can do the same in any convex $(n-1)$-gon, including the one formed by those points you give. – 2012-04-11
-
0Ah? I thought the points would satisfy the requirement in your answer. We have $n-1$ points on $y=e^x$, and a point $(0,0)$ below $y=e^x$. – 2012-04-12
-
0@FiniteA: I see now that the term "arching away" wasn't precise enough; sorry about that. I've edited the answer. – 2012-04-12