Sorting by Euclidean distance
Solution 1: Find the $\Theta(n^2)$ perpendicular bisectors between pairs of points, and construct the arrangement of these lines. The arrangement has $\Theta(n^4)$ cells, within which the sorted order is constant. So build a point location data structure for the arrangement, and decorate each cell with the sorted order that is to be returned for points within that cell. The sorted orders between adjacent cells differ only in a single transposition, so you can use a persistent data structure to allow the representations of these sorted orders to share space. Total space is $O(n^4)$ and query time is $O(\log n)$.

Solution 2: Choose a random sample of $\Theta(n)$ of these same perpendicular bisectors, construct their arrangement, and partition each arrangement cell by vertical line segments through each crossing of two sampled lines. The resulting partition has $\Theta(n^2)$ cells, each of which with high probability is crossed by $O(n)$ unsampled bisectors. Decorate each cell of the partition by a valid sorted ordering of the points as viewed from some x within the cell. Total space is $O(n^3)$.

Now, to do a query, locate the query point in the partition, look up the ordering stored with the partition cell, and use the Cartesian tree comparison sorting algorithm of Levcopoulos &amp; Petersson (1989) starting with this stored ordering. The time for this step is proportional to $\sum_i O(1+\log k_i)$ where $k_i$ is the number of points that are out-of-order with point $y_i$. But $\sum k_i$ is $O(n)$ (each unsampled bisector causes at most one out-of-order pair of points), so the query time $\sum_i O(1+\log k_i)$ is also $O(n)$.