performance - 计算一个单元格包含的圆圈数

Question

假设我们给了 n 个圆圈，它们构成了单元格 Ci。给出每个圆的中点(x-y 坐标)和半径。一个单元格的特征是它的弧线束缚了那个单元格。

对于每条弧线，都会给出以下信息:1.所属圆的中点2. 源点和目标点为 x-y 坐标，弧的起点和终点。3. 圆弧本身的中点也给出了它的 x-y 坐标。

对于 Cell1，我已将弧线涂成黄色、蓝色和棕色。另外，我试图在图片上指出圆弧的中点、目标和源。

现在，我想计算每个单元格包含的圆圈数，运行时间为 O(n²)。例如，单元格 C1 仅包含在 1 个圆圈中，单元格 C11 包含在 2 个中，C5 包含在 3 个中。

我的想法是在 O(m) 中计算它，其中 m:= 弧数。我认为一般情况下弧的数量可以超过n²。

任何帮助或想法将不胜感激!提前致谢。

Answer 1

我认为一般情况下弧的数量可以超过 n²。

你为什么这么认为？

任何一对圆最多相交于两个地方。所以单个圆最多会被分成2n - 2其他圆弧。因为有n圈子，最多有2n<sup>2</sup> - 2n = O(n<sup>2</sup>)圆弧。