1
$\begingroup$

If a point set in general position has $b$ convex hull points, it is known that the maximum number of triangles in any triangulation of the point set is $2n - 2 - b$ where $n$ is the number of points. Is any lower bound on the number of triangles known in terms of $b$ and $n$?

$\endgroup$

1 Answer 1

2
$\begingroup$

As long as you don't cheat (you don't have an edge of a triangle which contains more than $2$ points) you'll always have exactly $2n-2-b$ triangles in any triangulation of the point set.

A quick way to see this is to count the total sum of the angles over all the triangles in the decomposition. If your decomposition has $T$ triangles, then this sum will be $T\pi$, since the internal angles of any triangle add up to $\pi$. On the other hand, if there are $r$ internal points and $b$ convex hull points, each internal point contributes $2\pi$ to the angle sum, and each convex hull point contributes the corresponding internal angle of the convex hull. The sum of the internal angles of a $b$-gon is $(b-2)\pi$, so altogether we have $T\pi = 2r\pi + (b-2)\pi$, and $T = 2r + b-2$. Substituting $n=r+b$, you get your formula, $T = 2n-2-b$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .