4
$\begingroup$

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 ?

enter image description here

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 ?

$\endgroup$
4
  • $\begingroup$ I don't exactly follow your procedure for when the points are vertices of a convex polygon. If can maintain the rightmost visited points on the two chains, then the next point in the order is a neighbour (on the polygon) of one these points, as the polygon is convex. This means you can sort in $O(n)$ time for each rotation, no? What operation takes $O(n^2)$ time? $\endgroup$
    – Discrete lizard
    Jul 13, 2023 at 9:38
  • $\begingroup$ @Discretelizard: oops, my bad. The total time is $O(kn)$, with a maximum of $O(n^2)$. $\endgroup$
    – user16034
    Jul 13, 2023 at 9:41
  • $\begingroup$ If I understand correctly, you want some dynamic data-structure for which the "maintenance time" after $k$ rotations is better than $O(kn)$, and which represents the order of the sequence in some way? It would useful if you can clarify what type of queries you want to make on this data-structure. (output the full sequence? Find the next element? Find the position of an element?) $\endgroup$
    – Discrete lizard
    Jul 13, 2023 at 10:51
  • $\begingroup$ @Discretelizard: you are right, this is unclear. In fact my question is generic, and I would like to understand if there is a relation between the orders in two angular positions. Queries could be selection of the $k$-th (median), rank of a given point, find the next, closest to a fixed line... $\endgroup$
    – user16034
    Jul 13, 2023 at 11:52

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Interesting, thanks. This is a pure data-structure-based approach. I wonder if some geometric property could be exploited. $\endgroup$
    – user16034
    Jul 17, 2023 at 8:52
  • $\begingroup$ @YvesDaoust I've added another data structure for rank and predecessor/successor queries, which has a more geometric flavour. I think by using a different partition method you can probably also do selection (median) in quasi-linear preprocessing time and sublinear query time. $\endgroup$
    – Tassle
    Jul 17, 2023 at 9:00
  • $\begingroup$ @YvesDaoust: Also, the first data structure I give has essentially optimal space and preprocessing (up to subpolynomial factors). This is because this data structure allows us to do halfplane range searching (in the semi-group model) in logarithmic query time. Any data structure allowing for such queries in subpolynomial time requires essentially quadratic space. So for $k=\Theta(n^2)$ this is optimal. For the second data structure the best you can hope for with close to linear space is $O(\sqrt{n})$ query time (for similar reasons). $\endgroup$
    – Tassle
    Jul 17, 2023 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.