java - 在 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 个事件点的数组。授予每个圆圈有 2 个事件点:最左边的 x 和最右边的 x。调度程序有一个方法 sweepline() 来获取下一个事件点。

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

我也有状态。扫描线状态更精确。根据该理论，状态包含有资格相互比较的圈子。在整个故事中使用扫描线的意义在于，您可以排除很多候选人，因为他们根本不在当前圈子的半径范围内。

我用 TreeMap<Double, Circle> 实现了 Status .双正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)。我在这里错过了什么？非常欢迎你们提供任何意见。

提前致谢!

Answer 1

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

获取最大数量n² - n的一种方法交点是放置n的中心等半径圆 r在一条长度不同的点 l < 2r .