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)?

  • 2
    $\begingroup$ 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. $\endgroup$ – David Eppstein Mar 25 '12 at 16:43

Your Answer

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

Browse other questions tagged or ask your own question.