这个问题有些棘手。我编写了一个算法，用于将简单多边形分解为凸多边形，但现在我无法证明它不是最优的（即使用Steiner点（添加顶点）的最小凸多边形数）。我的教授坚称不能使用贪心算法，例如这个算法，但我想不出反例。
因此，如果有人能证明我的算法是次优的（或最优的），我会很感激。
用图片最容易解释我的算法（这些图片来自旧版本的次优解）：
我的算法是，在点i周围延伸线段，直到延伸线段与对面边缘上的顶点相遇。
如果在这个范围内没有顶点，则创建一个新的顶点（红点）并连接到该点：
如果在这个范围内存在一个或多个顶点，则连接到最近的那个。这通常会产生具有最少凸多边形数量的分解：
但是，在某些情况下，它会失败 - 在下面的图中，如果它恰好首先连接中间绿色线，则会创建一个额外的不必要的多边形。对此，我建议双重检查我们添加的所有边缘（对角线），并检查它们是否仍然必要。如果不需要，则删除它：
然而，在某些情况下，这还不够。看看这个图：
用a-c替换a-b和c-d将得到更好的解。在这种情况下，没有边缘可供删除，因此这是一个问题。在这种情况下，我建议按优先顺序选择：在决定将一个凹顶点连接到哪个顶点时，应选择具有最高优先级的顶点：
优先级低）最近的定点
优先级中）最近的凹顶点
优先级高）在向后处理时也在范围内的最近凹顶点（难以解释）--
在 此图 中，我们可以看到凹顶点9选择连接12（因为它最近），但连接5会更好。由于顶点5和12都在由延伸线段10-9和8-9定义的范围内，但是应该给顶点5优先权，因为9在4-5和6-5给定的范围内，但不在13-12和11-12给定的范围内。也就是说，边缘9-12消除了顶点9处的凹顶点，但未消除顶点12处的凹顶点，但可以消除顶点5处的凹顶点，因此应该给予顶点5优先权。
使用这个修改后的版本可能仍然存在边缘5-12，但可以在后处理期间将其删除。
assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]
for each vertex poly[i]
if poly[i] is reflex
find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
repeat for the ray given by poly[i+1], poly[i] (call this upper bound)
if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
connect poly[i] to this new point
else
iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
if poly[j] is a 'good reflex'
if no other good reflexes have been found
save it (overwrite any other vertex found)
else
if it is closer then the other good reflexes vertices, save it
else
if no good reflexes have been found and it is closer than the other vertices found, save it
connect poly[i] to the best candidate
repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save poly
结果我还有一个情况没有考虑到：[图5]
除非我再添加一个检查来确保算法能够连接顶点1和4，否则我的算法将尝试去连接他们。因此，我建议使用我之前提到的优先级方案，将所有“在范围内”的元素都塞进一个优先级队列里，然后取出优先级最高的元素，检查它是否能够连接，如果不能，则弹出并使用下一个。我认为，如果我对其进行正确的优化，这将使我的算法复杂度为O(r n log n)。
我制作了一个网站来大致描述我的发现。由于我喜欢移动东西，所以趁热打铁。
