用 O((n+s)log n) 的时间复杂度计算圆形的交点。

Question

我正在尝试设计一个算法，它可以以O((n+s) log n)的复杂度完成此任务。其中s是交叉点的数量。我尝试在互联网上搜索，但并没有找到类似的内容。

无论如何，我意识到这里关键是拥有一个良好的数据结构。我使用Java中的红黑树实现：TreeMap。我还使用了著名的扫描线算法来帮助我解决问题。

让我先解释一下我的设置。

我有一个调度器。这是一个基于最左坐标排序（升序）的PriorityQueue，其中包含我的圆形。scheduler.next()基本上轮询PriorityQueue，返回下一个最左边的圆形。

public Circle next()
{ return this.pq.poll();    }

我这里还有一个包含4n个事件点的数组。假设每个圆都有两个事件点：最左边的x和最右边的x。调度程序有一个名为sweepline()的方法，可以获取下一个事件点。

public Double sweepline()
{ return this.schedule[pointer++];    }

我也有一个状态。更确切地说，是扫描线状态。根据理论，该状态包含有资格相互比较的圆。在整个故事中拥有扫描线的意义在于，您能够排除许多候选项，因为它们根本不在当前圆的半径范围内。

我使用 TreeMap<Double, Circle> 实现了该状态。其中 Double 是 circle.getMostLeftCoord()。

该 TreeMap 可以保证插入/删除/查找的时间复杂度为 O(log n)。

算法本身的实现如下：

Double sweepLine = scheduler.sweepline();
Circle c = null;
while (notDone){
    while((!scheduler.isEmpty()) && (c = scheduler.next()).getMostLeftCoord() >= sweepLine)
        status.add(c);


    /*
     * Delete the oldest circles that the sweepline has left behind
     */
    while(status.oldestCircle().getMostRightCoord() < sweepLine)
        status.deleteOldest();

    Circle otherCircle;
    for(Map.Entry<Double, Circle> entry: status.keys()){
        otherCircle = entry.getValue();
        if(!c.equals(otherCircle)){
            Intersection[] is = Solver.findIntersection(c, otherCircle);
            if(is != null)
                for(Intersection intersection: is)
                    intersections.add(intersection);
        }
    }

    sweepLine = scheduler.sweepline();
}

编辑: Solver.findIntersection(c, otherCircle) 最多返回2个交点。重叠的圆不被视为有任何交点。

扫描线状态（SweepLineStatus）的代码

public class BetterSweepLineStatus {

TreeMap<Double, Circle> status = new TreeMap<Double, Circle>();

public void add(Circle c)
{ this.status.put(c.getMostLeftCoord(), c);     }

public void deleteOldest()
{ this.status.remove(status.firstKey());    }

public TreeMap<Double, Circle> circles()
{ return this.status;       }

public Set<Entry<Double, Circle>> keys()
{ return this.status.entrySet();    }

public Circle oldestCircle()
{ return this.status.get(this.status.firstKey());   }

我测试了我的程序，很明显它具有O(n^2)的复杂度。我错过了什么吗？欢迎大家提供任何意见。

提前感谢！

- xrdty

---

@G.Bach，虽然不太科学准确，但是运行几个测试实例就足以判断一个算法是O(n log n)、O(n²)还是O(2^n)。 - Daniel Brückner

@DanielBrückner 这绝对不够好，因为这是一个正式的陈述，而正式的陈述需要正式的证明。运行测试足以告诉您可以期望什么样的运行时间。它不是告诉复杂性的正确工具。 - G. Bach

@G.Bach 我并不需要任何正式的证明，但如果我设计了一个O(nlogn)算法，我至少希望它在我运行的每个情况下都能展现出其行为。在这种情况下，我只是想进行一个快速而简单的检查，以确定我是否做得正确。所有我的图表都显示出N加倍时呈指数增长的事实 - 对我来说 - 这绝对比O(N log N)更糟糕。 - xrdty

我正在尝试使用功率图构建一个解决方案，其可以在O(n log n)时间内完成，但是我不知道足够的信息来推断出解决方案是O((n+s) log n)。 如果对于每个圆，我们只需要检查它是否与相邻单元格相交，那么由于功率图中边的数量有限制，因此最多只需要进行O(n)次这样的检查就可以了。 但是，似乎一个圆与相邻单元格相交可能会与相邻单元格的相邻单元格相交，所以我卡住了。也许一些在功率图方面更有经验的人可以帮忙。 - obsolesced

另一个观察。正如被接受的答案指出的那样，在最坏情况下，交点数量是O(n^2)，因此在最坏情况下，O((n+s)log n)是O(n^2 log n)，这比比较每个圆对的O(n^2)方法更糟糕。除非有一些限制约束s所包含的圆，否则O((n+s) log n)算法与O(n^2)算法相比没有明显的优势。需要像@mic_e建议的O(n log n + s)这样更好的算法。 - obsolesced

Answer 1

你无法在O(n log n)的时间内找到平面上所有n个圆的交点，因为每对圆最多可以有两个不同的交点，因此n个圆最多可以有n²-n个不同的交点，所以不能在O(n log n)的时间内枚举它们。

一种获得最大数量的n²-n个交点的方法是将n个半径相等的圆的中心放置在长度为l < 2r的线的互不相同的点上。

- Daniel Brückner

---

请参考mcdowella的答案，了解如何排列这些圆形。 - G. Bach

问题仍然有效，但应该重新表述为：在O（nlogn + k）的时间复杂度内计算圆的交点，其中n是圆的数量，k是交点的数量。 - mic_e

Answer 2

使用相同中心和半径的N个圆将有N（N-1）/2对相交的圆，而通过使用足够大的圆使它们的边界几乎成为直线，您可以绘制一个具有N / 2条相交每个N / 2线的网格，这又是N ^ 2。我会查看在添加新圆时地图中通常存在多少条目。

您可以尝试为您的圆使用边界正方形，并在待处理正方形上保留索引，以便您只能找到与查询正方形相交的y坐标的正方形（假设扫描线与y轴平行）。这意味着-如果您的数据友好，您可以保存大量待处理的正方形，并仅检查其中的一些是否可能相交正方形内的圆。导致实际N ^ 2交集的不友好数据始终会是一个问题。

- mcdowella

---

我认为安排这些圆形可以根据圆的半径限制进行处理，因为建议的布局应该是“可缩放的”。 - G. Bach

@GBach - 我认为你是对的。这不仅仅是圆圈大小的问题，而是大小和相对位置的结合。我只是觉得站在一个比我大得多的圆圈旁边很方便，因为我所看到的一切都像一条直线。 - mcdowella

Answer 3

圆圈相对于整个区域有多大？如果比例足够小，我会考虑将它们放入某种桶中。这将使复杂度比 O(n log n) 稍微复杂一些，但应该会更快。

- jklsemicolon