计算O((n + s)log n)中的圆交点

Question

我试图弄清楚如何设计一个能够以O((n + s)log n)复杂度完成此任务的算法.是交叉点的数量.我试过在网上搜索,却找不到东西.

无论如何,我意识到拥有一个好的数据结构是关键.我在java:TreeMap中使用Red Black Tree实现.我还使用着名的(？)扫描线算法来帮助我处理我的问题.

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

我有一个调度程序.这是一个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>.双重是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.