Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
In 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? –  FiniteA Apr 11 '12 at 7:34
    
@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. –  joriki Apr 11 '12 at 7:39
    
My mistake. One last thing: would this point set works? {(0,0),(k, e^k) : k = 1..n-1.} –  FiniteA Apr 11 '12 at 7:56
    
@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. –  joriki Apr 11 '12 at 8:59
    
Ah? 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$. –  FiniteA Apr 12 '12 at 5:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.