Data structure for radial orderings of points on the plane
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.