是否有一种算法可以在线性时间（非线性预处理）中以不同方向的不同方向排序点？

发布于 2025-02-11 05:58:30 字数 471 浏览 1 评论 0原文

我在飞机上有一组点，我想根据遇到任意扫描线的何时进行排序。另一种定义是，我希望能够根据x -和y-坐标的任何线性组合对它们进行排序。我想在线性时间内进行排序，但是可以在二次时间的点集上进行预录（但最好是o（n log（n）））。这可能吗？我会喜欢与讨论此问题的论文的链接，但我自己找不到它。

例如，如果我有点（2,2），（3,0）和（0,3）我想能够对3x+2y的值进行对，并获得[（0,3），（3,0），（2,2），（2,2）]。

编辑：在下面的评论中，有用的评论者向我表明，枚举所有可能的扫描线的幼稚算法将给出o（n^2 log（n））预处理算法（再次感谢！）。是否可以具有o（n log（n））预处理算法？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

兔姬 2025-02-18 05:58:31

第一注意，列举所有扫描线的o（n^2 log（n）），但随后您必须对n^2扫描线进行排序。天真地这样做将花费时间o（n^3 log（n））和space o（n^3）。

我认为我可以将平均性能归于o（n），o（n^2 log*（n））时间和o（n^2）在预处理上花费的空间。（这里log*是迭代的logarithm 目的是一个常数。）但这只是平均表现，而不是最坏的情况。

要注意的第一件事是，有n选择2 = n*（n-1）/2对点。当我们旋转360度时，每对将两次跨过两次，最多o（n^2）不同的订购和o（n^2）。另请注意，一对交叉后，它不会再次交叉180度。在任何小于180度的范围内，给定的对将越过一次或不会穿越。

现在的想法是，我们将存储那些可能的订单的随机o（n），它们与它们相对应的扫描线。在任何扫描和下一个扫描线之间，我们将看到o（n^2 / n）= o（n）< / code>对点交叉。因此，这两种方式都是正确的o（1），并且我们想要的第一个和所需顺序之间的每一个倒置都是第一和第二种之间的反转。我们将使用它在o（n）中找到我们的最后排序。

让我向后填写细节。

我们的o（n）扫描线预先计算出来。时间o（log（n））我们找到了两个最近。假设我们找到以下数据结构。

pos1：从点到其在扫描中的位置的查找1。
points1：查找从扫描线1中的位置到点1。
points2：从位于扫描2中的点。

我们现在将尝试按时间进行分类o（n）。

我们初始化以下数据结构：

即将到来的：可能是下一个点的优先级队列。
IS_SEEN：位图从位置到我们是否添加了即将到来的要点。
答案：矢量/数组/您称之为语言的任何语言，它将在最后保存答案。
max_j：我们已添加到即将到来的第2行中的最远点。从-1开始。

现在我们要做以下操作。

for i in range(n):
    while is_seen[i] == 0:
        # Find another possible point
        max_j++
        point = points2[max_j]
        upcoming.add(point with where it is encountered as priority)
        is_seen[pos1[point]] = 1

    # upcoming has points1[i] and every point that can come before it.
    answer.append(upcoming.pop())

大力挥舞着我的手，每一点都被放入即将到来的一次，然后取出一次。平均而言，即将到来的具有o（1）点，因此所有操作平均为o（1）。由于有n点，因此总时间为o（n）。

好的，我们如何设置扫描线？由于我们只关心平均表现，因此我们作弊。我们随机选择o（n）对点。每对点都定义一个扫描线。我们在o（n log（n））中对那些扫描线进行排序。

现在，我们必须对o（n）扫描线进行排序。我们该怎么做？

好吧，我们可以通过我们想要的任何方法对固定数量进行排序。让我们选择4个均匀选择的扫描线，然后做到这一点。（实际上，我们只需要进行计算2倍。我们选择2对点。我们选择第一个2个交叉，然后是第二个2个十字的扫描线，然后其他2个扫描线从第一个2开始在180度处，因此之后，我们可以使用上面的算法对其他两个两个算法进行分类。并通过一分配到越来越小的间隔来做到这一点。

现在，当然，扫描线不会像上面那样接近。但是让我们注意，如果我们希望这些要点同意在平均o（f（n））扫描之间的位置，那么堆将具有o（f（n））< /code>其中的元素，并且对其进行操作将采用o（log（f（n）））时间，因此我们在o（n log（f（f（f（f（f（f（f（f（f（f（f（f（n））上））

。

1              .. n/log(n)
n/log(n)       .. n/log(log(n))
n/log(log(n))  .. n/log(log(log(n)))

n ..

在每个组中，我们都有o（n / log^k（n）） /代码>计算时间时间为o（n^2 log*（n））。

First note, that enumerating all of the sweeplines takes O(n^2 log(n)), but then you have to sort the n^2 sweeplines. Doing that naively will take time O(n^3 log(n)) and space O(n^3).

I think I can get average performance down to O(n) with O(n^2 log*(n)) time and O(n^2) space spent on preprocessing. (Here log* is the iterated logarithm and for all intents and purposes it is a constant.) But this is only average performance, not worst case.

The first thing to note is that there are n choose 2 = n*(n-1)/2 pairs of points. As we rotate 360 degrees, each pair will cross the other twice, for at most O(n^2) different orderings and O(n^2) pair crossings between them. Also note that after a pair crosses, it does not cross again for 180 degrees. Over any range of less than 180 degrees, a given pair either will cross once or won't.

Now the idea is that we'll store a random O(n) of those possible orderings and which sweepline they correspond to. Between any sweepline and the next, we'll see O(n^2 / n) = O(n) pairs of points cross. Therefore both sorts are correct to on average O(1), and every inversion between the first and the order we want is an inversion between the first and second sorts. We'll use this to find our final sort in O(n).

Let me fill in details backwards.

We have our O(n) sweeplines precalculated. In time O(log(n)) we find the two nearest. Let's assume we find the following data structures.

pos1: Lookup from point to its position in sweepline 1.
points1: Lookup from position to the point there in sweepline 1.
points2: Lookup from position to the point there in sweepline 2.

We will now try to sort in time O(n).

We initialize the following data structures:

upcoming: Priority queue of points that could be next.
is_seen: Bitmap from position to whether we've added the point to upcoming.
answer: A vector/array/whatever you language calls it that will hold the answer at the end.
max_j: The farthest point in line 2 that we have added to upcoming. Starts at -1.

And now we do the following.

for i in range(n):
    while is_seen[i] == 0:
        # Find another possible point
        max_j++
        point = points2[max_j]
        upcoming.add(point with where it is encountered as priority)
        is_seen[pos1[point]] = 1

    # upcoming has points1[i] and every point that can come before it.
    answer.append(upcoming.pop())

Waving my hands vigorously, every point is put into upcoming once, and taken out once. On average, upcoming has O(1) points in it, so all operations average out to O(1). Since there are n points, the total time is O(n).

OK, how do we set up our sweeplines? Since we only care about average performance, we cheat. We randomly choose O(n) pairs of points. Each pair of points defines a sweepline. We sort those sweeplines in O(n log(n)).

Now we have to sort O(n) sweeplines. How do we do this?

Well we can sort a fixed number of them by any method we want. Let's pick 4 evenly chosen sweeplines and do that. (We actually only need to do the calculation 2x. We pick 2 pairs of points. We pick the sweepline where the first 2 cross, then the second 2 cross, then the other 2 sweeplines are at 180 degrees from the first 2, and therefore are just reversed order.) After that, we can use the algorithm above to sort a sweepline between 2 others. And do that through bisection to smaller and smaller intervals.

Now, of course, the sweeplines will not be as close as they were above. But let's note that if we expect the points to agree to within an average O(f(n)) places between the sweepline, then the heap will have O(f(n)) elements in it, and operations on it will take O(log(f(n))) time, and so we get the intermediate sweepline in O(n log(f(n)). How long is the whole calculation?

Well, we have kind of a tree of calculations to do. Let's divide the sweeplines by what level they are, the group them. The grouping will be the top:

1              .. n/log(n)
n/log(n)       .. n/log(log(n))
n/log(log(n))  .. n/log(log(log(n)))

...and so on.

In each group we have O(n / log^k(n)) sweeplines to calculate. Each sweepline takes O(n log^k(n)) time to calculate. Therefore each level takes O(n^2). The number of levels is the iterated logarithm, log*(n). So total preprocessing time is O(n^2 log*(n)).

回复收藏 0 原文

~没有更多了~