Rotating sort algorithm

Question

Take a set of $n$ points in the plane. You want to sort them by increasing abscissa. But you also want to sort them by abscissa after several arbitrary rotations, say $k$, in increasing angles.

The obvious brute-force solution takes time $O(kn\log n)$. Is there a method with a better complexity ?

If one considers a full rotation of the point cloud, there will be $\frac{n(n-1)}2$ swaps in total, corresponding to all directions formed by pairs of points. This hints that the problem could be $\Omega(n^2)$, unfortunately.

If the points are the vertices of a convex polygon, after sorting the vertices in two monotone chains, we can restore the order after every rotation by delimiting the next two monotone chains and merging them. The total time is $O(kn)$.

But what if we don't need an explicit enumeration of the sorted sequence, but instead a suitable update of a search tree ?

Answer 1

In everything which follows I assume general position of the points (no 3 colinear points), mostly for simplicity.

This is might not be exactly what you are looking for, but you can build a data structure with $O(n^2\log n)$ preprocessing time and $O(n^2)$ space which allows you to navigate a balanced binary search tree corresponding to any angle in $O(\log n)$ time (plus whatever time your query takes to look at stuff in the search tree, which is probably also $O(\log n)$).

For rank and predecessor/successor queries specifically, you can also do $O(n\log^2 n)$ preprocessing time, $O(n)$ space and $O(n^{\log_4 3}) \approx O(n^{0.7925})$ query time.

__

For the first data structure, you can do this using (for example) a partially persistent red-black tree. A partially persistent red-black tree allows you to insert/delete elements in $O(\log n)$ time and $O(1)$ space increase, and search in any previous version of the tree in $O(\log n)$ time.

So start by inserting all your points in the BST according to their initial order by $x$ coordinate.

Now do the following: sort the pairs of points according to the angle made by the line passing through them. Each pair corresponds to one swap in the order of points as you rotate the plane. For each pair of points (in sorted order by angle), delete them from the BST and reinsert them according to the order after they swap. This costs $O(n^2\log n)$ time and results in a data structure taking $O(n^2)$ space.

Now given some arbitrary angle, you can find the correct version of the BST in $O(\log n)$ time and then do whatever you want in it (as long as you don't modify it).

If you were to do all of this without persistence then you would have $O(n^3\log n)$ preprocessing time and $O(n^3)$ space, so this is a win, even if it doesn't buy you anything when $k$ is small.

__

For the second data structure, we will build a partition tree on the points based on the ham sandwich theorem. A consequence of the ham sandwich theorem in the plane is the following:

• For any set of $n$ points in the plane, there exists two lines which partition the plane into $4$ regions each containing at most $\lceil n/4 \rceil$ points. Moreover, it is not too hard to show (or to look up a proof) that you can find such two lines in $O(n\log n)$ time.

So we build a partition tree of the plane by recursively applying this result until we reach sets of constant size. Each node also stores the number of points in its subtree. This is our data structure.

Let's see how to perform a rank query using this data structure. I will describe the queries for the pointset without rotation applied to it, but you can adapt it for any rotation by replacing the vertical lines I will use here with rotated lines.

Given some $x$-coordinate $x_0$, we want to find the number of points left of the line $\ell:x=x_0$. We are at the root of the partition tree. Notice that the line $\ell$ intersects at most $3$ of the $4$ regions which partition the plane at this level. We need to recurse on these $3$ regions we recurse. For the other, non-intersected region, we can know directly whether all points inside lie to the left or right of $\ell$ so we add that to the total as needed. This leads to a recursion on the runtime of $T(n) = 3T(n/4) + O(1)$, yielding $T(n) = O(n^{\log_4 3})$.

Successor/predecessor queries are done similarly.

You can almost certainly improve query runtime by using more modern partition methods, but this is the only thing I can whip up on the spot. I think there are methods which can also shave a log factor on the preprocessing time.