c - 通过选择圆周上的点将圆分成几部分？

在一个圆上，在其圆周上选择 N 个任意点。由这 N 个点形成的完整图形会将圆的面积分成许多部分。

沿圆周选择点时，该圆最多可以分成多少个区域？

例子:

2 分 => 2 件

4 分 => 8 件

任何想法如何解决这个问题？

最佳答案

这称为 Moser's circle problem 。

解决办法是:

IE。

证明很简单:

考虑圆内的每个交叉点。它必须由两条线的交点来定义，每条线都有两个点，所以圆内的每个交点都定义了圆周上的 4 组独特的点。因此，最多有 n choose 4 内部顶点，显然圆周上有 n 顶点。

现在，每个顶点接触多少条边？嗯，这是一个完整的图，所以外面的每个顶点都接触 n - 1 边，当然里面的每个顶点都接触 4 边。所以边的数量由 (n(n - 1) + 4(n choose 4))/2 给出(我们除以二，否则每条边将被它的两个顶点计算两次)。

最后一步是使用欧拉公式计算图中的面数，即:v - e + f = 1(在我们的例子中 Euler characteristic 为 1)。

解决 f 给出了上面的公式:-)