Data structure for radial orderings of points on the plane

Question

Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$.

Consider shooting an upward vertical ray from $x$, and rotate the ray counterclockwise. The sequence of points in $S$ swept through by the ray is the radial ordering.

Given a set of $n$ points on the plane. Create a data structure, so it can answer the following query:

Query($x$,$i$)

Input: $x\in S$, $1\leq i\leq n-1$.

Output: The $i$th element in the radial ordering with respect to $x\in S$.

Is there any study on such a data structure? In my application, there will be around $\tilde{O}(n)$ queries.

Answer 1

This problem is the same as halfspace range counting up to polylog factors.

Halfspace range counting in 2D

Preprocess $n$ points $S$ on the plane. A query takes a halfspace $H$ (represented by the boundary), and return $|H\cap S|$.

For the case of $\tilde{O}(n)$ queries, one can use $\tilde{O}(n^{4/3})$ time to build a data structure that returns the answer in $\tilde{O}(n^{1/3})$ time. This is the best possible up to polylog factors [1].

Proof Sketch:

Upper bound:

The simplex partition tree data structure for halfspace range counting [1] can be used directly for this problem. A simple solution would be using a halfspace counting query as a proxy for binary search while navigating the partition tree. I believe polylog factors can be saved with more care.

Lower bound:

Consider we want to solve the halfspace range counting problem in 2D on $S$, we first construct the radial orderings data structure.

For any halfspace $H$ as input, we shift the halfspace up until it touches an element in $S$. By duality, this operation can be modeled as a vertical ray shooting problem in a convex polygon defined by the intersection of halfspaces, which is known to be very fast [2].

We can use our data structure to do binary search. We find two adjacent points in the radial ordering so the slope of $H$ is in between. The index shows the number of points in $H\cap S$.

1. Matoušek, Jiří, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom. 10, No. 2, 157-182 (1993). ZBL0774.68101.

2. Agarwal, Pankaj K.; Matoušek, Jiří, Ray shooting and parametric search, SIAM J. Comput. 22, No. 4, 794-806 (1993). ZBL0777.68042.

Answer 2

One approach would be to use a k-d tree. You can use the k-d tree to answer the following query:

Count($x$, $\theta$):

Input: $x \in S$, $0 \le \theta < 2\pi$.

Output: The number of points $y \in S$ such that the angle between a vertical line through $x$ and a line from $x$ to $y$ is at most $\theta$.

A procedure for answering Count queries can be used to answer your queries, through binary search on $\theta$.

To answer Count queries with a k-d tree, note that each node of the k-d tree corresponds to a region $R$ of space. Augment each node with the number of points in that region (a one-time preprocessing). Now, when answering queries, recursively traverse the tree. If $x \notin R$, and either all of $R$ makes an angle with $x$ that is $\le \theta$ or all of $R$ makes an angle that is $>\theta$, you don't need to recurse into that node of the k-d tree; you can just use the count associated with that node. Otherwise, recurse. You can tell whether this condition holds by computing the angle from $x$ to each corner of $R$. This gives you a procedure for answering Count queries more efficiently than enumerating all points in $S$.

I don't know what the worst-case asymptotic running time will be, but it might be a pragmatic solution. I don't know if you can efficiently answer your queries directly on the k-d tree rather than working indirectly via Count queries.