# Data structure for radial orderings of points on the plane

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.

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.

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.

• Thank you. Indeed I don't think this can improve asymptotics, as the angle ranges can overlap a lot. – Chao Xu Apr 2 at 5:08