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.
-
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