3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.