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$.


Matoušek, Jiří, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom. 10, No. 2, 157-182 (1993). ZBL0774.68101.
Agarwal, Pankaj K.; Matoušek, Jiří, Ray shooting and parametric search, SIAM J. Comput. 22, No. 4, 794-806 (1993). ZBL0777.68042.