0
$\begingroup$

Suppose there are $n$ points in $\mathbb{R}^2$ in general position that we need to triangulate, and for simplicity's sake their convex hull is a triangle. Define the triangle count as the number of point triplets connected pairwise by edges, including those enclosing other points and edges.

enter image description here

  • (a) there are 4 points and 4 triangles, including ABC.
  • (b) Delaunay triangulation of 6 points creating 8 triangles: the hull ABC, the innermost triangle DEF and the 6 triangles between them.
  • (c) a different triangulation of the same 6 points creating 10 triangles, because ADC and ADB have 4 triangles each as in (a).

Consider the following procedure: pick a point inside a triangle and connect it to the triangle's vertices. It can be shown via induction that starting with the outermost shape and recursively applying this procedure always yields $3n - 8$ triangles, giving a lower bound. This is how I obtained the example (c).

My question is whether this algorithm is optimal or there are examples of triangulations of $n$ points with more than $3n-8$ triangles.

I don't even know if this is a simple problem and if there is an exact solution, so any hints would be appreciated.

$\endgroup$
1
  • $\begingroup$ You can obtain higher numbers if points happen to be collinear.As for the non-colinear case, note that the number of "small" triangles stays the same regardless of what triangulation you pick:$2n-5$.You can arrange your general triangles in a "tree" with bigger triangles spawning smaller ones as children.You want to maximize the number of nodes in the tree.The tree has $2n-5$ leafs and the constraint that a non-leaf node must have at least 3 children.(A non-empty triangle has at least 3 sub-triangles,those spawned by its 3 sides on its interior).I think you get $3n-8$ max, haven't checked yet. $\endgroup$ Sep 18 '17 at 8:47
1
$\begingroup$

If we allow arbitrary co-linearity, $\frac{(n-2)(n-1)}{2}$ is the maximum: simply put $n-1$ points on a side, and $1$ on the outside, and count the formed triangles.

When no $3$ points are collinear, $3n-8$ is the optimal answer.

It can be proved by induction. Denote $T(n)$ to be the maximum number of triangles obtained in a triangulation of $n$ points. Your example shows $T(4) = 4$ , $T(6)= 10$. For ease of computation, consider $m$ points inside a convex-hull triangle formed by 3 additional points. Denote $S(m)$ to be the maximum number of triangles formed in triangulating those $m+3$ points, In other words, $S(m)=T(m+3)$. We shall be maximising $S(m)$.

We call a triangle 'minimal' , if it contains no points inside. We shall count the number of minimal triangles. Consider a polyhedron of only triangular faces. Each face has $3$ edges, and each edge appears on $2$ faces. So we have $\frac{3}{2}F$ = $E$, where $F$ is the number of faces, $E$ the number of edges. The formula for the Euler characteristic, says $F+V - E = 2$, where $V$ is the number of vertices/points in our polyhedron. So we have $V - \frac{1}{2}F=2$, or $F=2V-4$. That is, a (convex) polyhedron with $V$ vertices and only triangular faces will have $2V-4$ faces.

How does that tie in to our triangulation? By removing a face of our polihedron, and "streching" its edges, and then projecting onto a plane, they become the edges of the convex hull. The minimal triangles in our triangulation corespond to the other faces of our polyhedron. So a triangulation of $V$ points will have exactly $2V-4-1 = 2V-5$ minimal triangles, regardless of our mode of triangulation. (note that both your second and third examples have $2*6-5=7$ minimal triangles). This also forms the "worst-case" scenario. No triangulation will have less than $2n-5 + 1$ total triangles. The worst-case scenario is achieved when the only non-minimal triangle is the convex-hull.

We need to organize our triangles:

Lemma: of any two triangles, either one will be included in the other, or the two will have disjoint interiors:

Proof: the only alternative is that the boundaries of the triangles intersect in a denoted vertex/point. That leads to the existence of collinear points, contradicting our hypothesis.

Therefore, our triangles can be organized into a tree, with a triangle $A$ being a child of a triangle $B$ if and only if $A\subset B$, and there exists no intermediate triangle $C$ such that $A\subset C \subset B$. The root of our tree is the largest triangle, the convex hull. The total number of triangles of a particular triangulation is the number of nodes in its tree. We associate to the root of a tree a number $m=n-3$, denoting the number of points contained in the interior of the root-triangle.

We study the properties of our tree: the leaves of our tree correspond to minimal triangles. Our tree has $2n-5 = 2(m+3)-5 = 2m+1$ leaves. If it has the maximum number of nodes $T(m)$ for a given $m$ associated with its root, then the same property holds for all its sub-trees. (if the tree is optimized, so are its children). Additionally, any node is either a leaf or has at least $3$ children. (if a triangle is not minimal, there are at least $3$ children sub-triangles, those associated with its edges.) . Any node that is not a leaf has an odd number of children (if we eliminate all vertices at deeper levels such that the children become leaves, we are left with $k$ vertices and $2k+1$ children)

Assume we've proved inductively up to $m< k$ that a tree with $m$ associated at its root has a maximum of $3m+1$ nodes. (that is, a triangulation with $m+3$ points has a maximum of $3m+1$ triangles).

Set $m=k$. Let the tree have $2p+1$ children. $S(m)$ stands both for the maximum number of triangles of $m+3$ points, and for the maximum number of nodes of a tree with $m$ associated to its root.

$S(k) = 1 + S(n_{1})+S(n_{2})+...+S(n_{2p+1})$, where $(n_{1}+n_{2}+...n_{2p+1})=k-p$,

$1$ is for the top-node, $S(n_{y})$ the number of nodes in the $y$'th child.

$p$ points/vertices were used to construct the top-level split of the hull in $2p+1$ triangles, and the rest of the $k-p$ vertices are to be found in the interior of those triangles. Since there are at least $3$ children, we have $p\geq1$, $(n_{1}+n_{2}+...n_{2p+1})\leq k-1$. This gives $n_{y}\leq k-1 ,\forall y$.

We've proved inductively that $S(m) = 3m+1$ for $m<k$ . This gives: $S(k) =1 + (3n_{1}+1)+(3n_{2}+1)+...+(3n_{2p+1}+1) =$

$= 1 + 3(n_{1}+n_{2}+...n_{2p+1}) + 2p + 1 =$

$=3(k-p) + 2p + 2 = $

$=3k + 2 -p$.

This maximizes when $p$ is minimized. This gives $p=1$ and a splitting of the convex hull-triangle into exactly $2p+1 = 3$ children.

$S(k)=3k+1$, completing the inductive proof. Substitute $k=n-3$, and we get $3n-8$ triangles for $n$ vertices.

The optimum is $3n-8$, obtained when every triangle is either empty, or splits into exactly $3$- children triangles. At your $(b)$ example, $ABC$ splits into $7$ children, so it's suboptimal. At your $(c)$ example:

$ABC$ split into $ABD,BCD,CAD$,

$CAD$ splits into $CAE,AED,DEC$,

$ABD$ splits into $ABF,BDF,DAF$,

$BCD$ is empty/minimal.

Thus, the $(c)$ example is optimal whilst the $(b)$ one is not.

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed proof. While I haven't had the time to go over every detail, the ideas outlined in your comment alone have been very helpful for sure. The main point to gain intuition here was that since the number of leaves is fixed, what we really want to do is to maximise the number of inner nodes (or layers) in our tree, and that can be of course achieved by branching as often as possible, with non-leaf nodes having three children each. Thanks again! $\endgroup$
    – Norrius
    Sep 18 '17 at 20:21

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.