考察三角剖分对应的平面图，设其最外圈的点数为 $$$x$$$，三角形的数量为 $$$m$$$。由平面图欧拉公式得 $$$V+F-E=1$$$，又由 $$$F\ge m, E= \dfrac{3F+x}2$$$ 得 $$$m\le F=2(n-1)-x$$$。于是问题转化为最小化这个 $$$x$$$ 并顺手取到等号。

来看哪些点一定会出现在最外圈。肉眼瞪得，当以这点为原点时，若存在某个象限内没有其他点，则该点一定在最外圈。下面进行构造使得所有等号均成立。

将所有点按纵坐标从小到大排序，依次加入，同时维护两个单调栈 $$$q_1,q_2$$$，其中 $$$x_{q_{1,i}} \gt x_{q_{1,i-1}},y_{q_{1,i}} \gt y_{q_{1,i-1}}$$$；$$$x_{q_{2,i}} \lt x_{q_{2,i-1}},y_{q_{2,i}} \gt y_{q_{2,i-1}}$$$ 且两栈栈顶元素相同。当加入点 $$$(x_i,y_i)$$$ 时，依次对两栈做如下更新：

若 $$$q_1$$$ 不为空，取出 $$$q_1$$$ 栈顶元素 $$$j$$$，若 $$$x_i \lt x_j$$$，弹栈，且若栈仍非空，取其栈顶 $$$k$$$，将 $$$(i,j,k)$$$ 加入 $$$T$$$。重复执行这一步直到 $$$x_i \gt x_j$$$；若 $$$q_2$$$ 不为空，取出 $$$q_2$$$ 栈顶元素 $$$j$$$，若 $$$x_i \gt x_j$$$，弹栈，且若栈仍非空，取其栈顶 $$$k$$$，将 $$$(i,j,k)$$$ 加入 $$$T$$$。重复执行这一步直到 $$$x_i \lt x_j$$$。容易验证这给出了一个取等。