algorithm - 三角划分

Question

这是 2010 年太平洋 ACM-ICPC 竞赛中的一个问题。它的要点是试图找到一种方法将三角形内的一组点划分为三个子三角形，使得每个分区恰好包含三分之一的点。

输入:

• 边界三角形的坐标:(v1x,v1y),(v2x,v2y),(v3x,v3y)
• 一个号码 3n < 30000表示位于三角形内的点数
• 3n 的坐标点数:(x_i,y_i)对于 i=1...3n

输出:

• 一个点(sx,sy)将三角形分成 3 个子三角形，使得每个子三角形恰好包含 n点数。

split 点将边界三角形 split 成子三角形的方式如下:从 split 点到三个顶点分别画一条线。这会将三角形分成 3 个子三角形。

我们保证存在这样的点。任何这样的点就足够了(答案不一定是唯一的)。

这是 n=2 的问题示例(6 分)。我们得到了每个彩色点的坐标和大三角形每个顶点的坐标。 split 点以灰色圈出。

有人能推荐一个比 O(n^2) 更快的算法吗？ ？

Answer 1

这是一个O(n log n) 算法。让我们假设没有退化。

高级思想是，给定一个三角形PQR，

   P
  C \
 /  S\
R-----Q

我们最初将中心点 C 放置在 P 处。将 C 滑向 R 直到三角形 CPQ 内有 n 个点和一个(S) 在 CQ 段上。将 C 滑向 Q 直到三角形 CRP 不再不足(扰动 C 并且我们完成)或CP 击中一个点。在后一种情况下，将 C 从 P 滑开，直到三角形 CRP 不再不足(我们已经完成)或 CQ 击中一个点，在这种情况下，我们开始再次将 C 滑向 Q。

很明显，实现不能“滑动”点，因此对于涉及 C 的每个三角形，对于该三角形的每个顶点 S 而不是 C ，将三角形内的点存储在按角度排序的二叉搜索树中，S。这些结构足以实现该动力学算法。

我在没有证据的情况下断言这个算法是正确的。

至于运行时间，每个事件都是一个点线交点，可以在O(log n)时间处理。角度 PC 和 QC 和 RC 都是单调的，所以每条 O(1) 线都命中每个点最多一次。