# Triangulation with maximum greatest area

Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define

$$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$

which denotes the series of interior angles of $T$, sorted in ascending order. We can compare two such series (of the same length) easily in lexicographical order. We know that $T$ is a Delaunay-Triangulation iff $\alpha(T) \geq \alpha(T')$ for all possible triangulations $T'$ of $P$. This is also called the "maximum smallest angle" characteristic of the Delaunay Triangulation.

My question is now, is there a "maximum greatest area" triangulation? (Yes, not "maximum smallest area"!) More formally, define

$$A(T) = (A_1, A_2, \ldots, A_d)$$

which denotes the series of triangle areas of $T$, sorted in descending order, and I hope to find a triangulation $T$, so that $A(T) \geq A(T')$ for all possible triangulations $T'$ of $P$.

Does anyone know such an algorithm, or is it even trivially computable (i.e. with a greedy algorithm)?

• I think as you suggest it's trivially computable by a greedy algorithm when there are no ties ub the area between two different triangles. When there are ties, it might be more difficult. – David Eppstein Mar 25 '12 at 16:43