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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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