<p>This problem is the same as halfspace range counting up to polylog factors. </p>

<blockquote>
  <p><strong>Halfspace range counting in 2D</strong></p>
  
  <p>Preprocess <span class="math-container">$n$</span> points <span class="math-container">$S$</span> on the plane. A query takes a halfspace <span class="math-container">$H$</span> (represented by the boundary), and return <span class="math-container">$|H\cap S|$</span>.</p>
</blockquote>

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

<p>Proof Sketch:</p>

<p><strong>Upper bound</strong>:</p>

<p>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. </p>

<p><strong>Lower bound</strong>:</p>

<p>Consider we want to solve the halfspace range counting problem in 2D on <span class="math-container">$S$</span>,
we first construct the radial orderings data structure.</p>

<p>For any halfspace <span class="math-container">$H$</span> as input, we shift the halfspace up until it touches an element in <span class="math-container">$S$</span>. 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].  </p>

<p>We can use our data structure to do binary search. We find two adjacent points in the radial ordering so the slope of <span class="math-container">$H$</span> is in between. The index shows the number of points in <span class="math-container">$H\cap S$</span>.</p>

<ol>
<li><p><em>Matoušek, Jiří</em>, <a href="http://dx.doi.org/10.1007/BF02573972" rel="nofollow noreferrer"><strong>Range searching with efficient hierarchical cuttings</strong></a>, Discrete Comput. Geom. 10, No. 2, 157-182 (1993). <a href="https://zbmath.org/?q=an:0774.68101" rel="nofollow noreferrer">ZBL0774.68101</a>.</p></li>
<li><p><em>Agarwal, Pankaj K.; Matoušek, Jiří</em>, <a href="http://dx.doi.org/10.1137/0222051" rel="nofollow noreferrer"><strong>Ray shooting and parametric search</strong></a>, SIAM J. Comput. 22, No. 4, 794-806 (1993). <a href="https://zbmath.org/?q=an:0777.68042" rel="nofollow noreferrer">ZBL0777.68042</a>.</p></li>
</ol>

CC BY-SA 4.0
2019-04-02T16:58:08.983Z
2019-04-02T17:33:21.080Z
2019-04-02T17:33:21.080Z
Chao Xu
<p>One approach would be to use a k-d tree.  You can use the k-d tree to answer the following query:</p>

<p>Count(<span class="math-container">$x$</span>, <span class="math-container">$\theta$</span>):</p>

<p><strong>Input:</strong> <span class="math-container">$x \in S$</span>, <span class="math-container">$0 \le \theta &lt; 2\pi$</span>.</p>

<p><strong>Output:</strong> The number of points <span class="math-container">$y \in S$</span> such that the angle between a vertical line through <span class="math-container">$x$</span> and a line from <span class="math-container">$x$</span> to <span class="math-container">$y$</span> is at most <span class="math-container">$\theta$</span>.</p>

<p>A procedure for answering Count queries can be used to answer your queries, through binary search on <span class="math-container">$\theta$</span>.</p>

<p>To answer Count queries with a k-d tree, note that each node of the k-d tree corresponds to a region <span class="math-container">$R$</span> 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 <span class="math-container">$x \notin R$</span>, and either all of <span class="math-container">$R$</span> makes an angle with <span class="math-container">$x$</span> that is <span class="math-container">$\le \theta$</span> or all of <span class="math-container">$R$</span> makes an angle that is <span class="math-container">$&gt;\theta$</span>, 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 <span class="math-container">$x$</span> to each corner of <span class="math-container">$R$</span>.  This gives you a procedure for answering Count queries more efficiently than enumerating all points in <span class="math-container">$S$</span>.</p>

<p>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.</p>

CC BY-SA 4.0
2019-04-02T05:08:06.043Z
Thank you. Indeed I don't think this can improve asymptotics, as the angle ranges can overlap a lot.
Chao Xu
CC BY-SA 4.0
2019-03-31T20:26:00.127Z
2019-03-31T20:26:00.127Z
D.W.
<p>Assume points are always in general position.
For a set of <span class="math-container">$n$</span> points <span class="math-container">$S$</span> on the plane, a radial ordering with respect to <span class="math-container">$x\in S$</span> is a total ordering of the elements in <span class="math-container">$S-x$</span>. </p>

<p>Consider shooting an upward vertical ray from <span class="math-container">$x$</span>, and rotate the ray counterclockwise. The sequence of points in <span class="math-container">$S$</span> swept through by the ray is the radial ordering. </p>

<p>Given a set of <span class="math-container">$n$</span> points on the plane. Create a data structure, so it can answer the following query:</p>

<blockquote>
  <p>Query(<span class="math-container">$x$</span>,<span class="math-container">$i$</span>)</p>
  
  <p><strong>Input</strong>: <span class="math-container">$x\in S$</span>, <span class="math-container">$1\leq i\leq n-1$</span>.</p>
  
  <p><strong>Output</strong>: The <span class="math-container">$i$</span>th element in the radial ordering with respect to <span class="math-container">$x\in S$</span>.</p>
</blockquote>

<p>Is there any study on such a data structure? 
In my application, there will be around <span class="math-container">$\tilde{O}(n)$</span> queries. </p>

<ds.data-structures><computational-geometry>
Data structure for radial orderings of points on the plane
Chao Xu
# Data structure for radial orderings of points on the plane

(Asked by: username_0 on 2019-03-30)

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.

**Tags:** ds.data-structures, computational-geometry


---

## 2 answers

### Answer by username_0 on 2019-04-02. Score: 2 | Accepted answer

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**](http://dx.doi.org/10.1007/BF02573972), Discrete Comput. Geom. 10, No. 2, 157-182 (1993). [ZBL0774.68101](https://zbmath.org/?q=an:0774.68101).
2. *Agarwal, Pankaj K.; Matoušek, Jiří*, [**Ray shooting and parametric search**](http://dx.doi.org/10.1137/0222051), SIAM J. Comput. 22, No. 4, 794-806 (1993). [ZBL0777.68042](https://zbmath.org/?q=an:0777.68042).


---

### Answer by username_1 on 2019-03-31. Score: 1

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.

> **Comments:**
> **username_0**: Thank you. Indeed I don't think this can improve asymptotics, as the angle ranges can overlap a lot.  

---

