Finding nearest of a list of points on Euclidian plane to a given reference point
You can build a 2d binary search tree for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that circle.