Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$.
A no-brain approach is to calculate distances between $x$ and $y$ for all $y \in S$ and then sort them using any fast algorithm.
Is there any way to store or preprocess $S$ so the sorting process becomes faster?
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 & 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)$.
You're probably not going to be able to get away from $n\log(n)$ time any way you slice it; even precomputing regions corresponding to all possible sort orders could (I believe) yield $O(n!)$ regions and thus finding 'your' region by any meaningful search technique will take $O(\log(n!)) = O(n\log(n))$ time. (EDIT: this is absolutely wrong; see David Eppstein's excellent answer for more information!) One useful way of getting the complexity down, on the other hand - especially if you don't need the full sort at once but just need to be able to randomly pull out $k$th-nearest on the fly - might be through higher-order Voronoi diagrams: extensions of the standard Voronoi cell that accomodate not just the nearest neighbor but second-nearest, etc. Frank Dehne's paper on k-nearest neighbor searching, http://people.scs.carleton.ca/~dehne/publications/2-02.pdf seems to be the canonical reference; his homepage at http://www.dehne.carleton.ca/publications has a number of other papers on Voronoi diagrams that might be of some use.
