<p>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.  (<strong>EDIT:</strong> 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, <a href="http://people.scs.carleton.ca/~dehne/publications/2-02.pdf" rel="nofollow">http://people.scs.carleton.ca/~dehne/publications/2-02.pdf</a> seems to be the canonical reference; his homepage at <a href="http://www.dehne.carleton.ca/publications" rel="nofollow">http://www.dehne.carleton.ca/publications</a> has a number of other papers on Voronoi diagrams that might be of some use.</p>

CC BY-SA 3.0
2011-10-24T22:13:32.730Z
If one partitions the plane into regions with different sort orders, there are $\Theta(n^4)$ regions, not $O(n!)$. The boundaries between regions are the perpendicular bisector lines of pairs of points, there are $\Theta(n^2)$ such lines, and the set of regions is given by the arrangement of these lines.
David Eppstein
CC BY-SA 3.0
2011-10-24T22:42:06.380Z
@David I think you should make this an answer.
James King
CC BY-SA 3.0
2011-10-24T23:19:10.707Z
Seconded - n! felt wrong as I was writing it, but I couldn't see a case against.  I'll amend my answer shortly to correct that, but I'd really like to see a more directly-informed one; thank you!
Steven Stadnicki
CC BY-SA 3.0
2011-10-24T19:23:14.787Z
2011-10-25T00:16:30.887Z
2011-10-25T00:16:30.887Z
Steven Stadnicki
<p>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)$.</p>

<p>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)$.</p>

<p>Now, to do a query, locate the query point in the partition, look up the ordering stored with the partition cell, and use the <a href="http://en.wikipedia.org/wiki/Cartesian_tree">Cartesian tree</a> 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)$.</p>

CC BY-SA 3.0
2011-10-25T23:22:45.653Z
PS here's an alternative variant of solution 2 that uses the same space and query time but trades off a more complicated preprocessing algorithm for a simpler query algorithm: http://11011110.livejournal.com/233793.html
David Eppstein
CC BY-SA 3.0
2011-10-26T14:19:35.083Z
Why do $n^4$ pre-processing when you could sort from all $n$ starting points in $O(n^2\log n)$ time and store the results in a hash table using space $O(n^2)$ for constant lookup?
Dave
CC BY-SA 3.0
2011-10-26T14:41:16.367Z
Because there are $\Theta(n^4)$ starting points with different sort orders, not $\Theta(n^2)$.
David Eppstein
CC BY-SA 3.0
2011-10-24T23:59:33.400Z
2011-10-24T23:59:33.400Z
David Eppstein
<p>$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$.</p>

<p>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.</p>

<p>Is there any way to store or preprocess $S$ so the sorting process becomes faster?</p>

CC BY-SA 3.0
2011-10-24T15:03:35.793Z
You can consider a grid of appropriate size and group points by corresponding square (using, say, hash table). Then for certain pairs of squares you can infer that all points from one square are farther from $x$ than all points from another square. In practice it could help, I guess.
ilyaraz
CC BY-SA 3.0
2011-10-24T15:36:03.733Z
The “no-brain approach” which you stated runs in O(n log n) time, where n is the number of points in S, which I guess is pretty fast in practice.  Do you want to shove off the log n factor, or do you want something else such as [external sorting](http://en.wikipedia.org/wiki/External_sorting)?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-24T17:38:27.350Z
The point is that I have practically unlimited time to prepare my set of points, but the time to sort them is very much limited. That said, any speed-up of standard sorting is appreciated - even if it is same O(n log n), but faster in worst case (or best case, or whatever).
Alex K.
CC BY-SA 3.0
2011-10-24T17:40:59.017Z
For example, if I store S as a 2-d-tree, I can find one nearest neighbour in O(log n) time. Maybe there is a similar solution for my task. I'm not a great expert in spatial data structures - and there is so many of them - I could easily miss it.
Alex K.
<cg.comp-geom><sorting>
Sorting by Euclidean distance
Alex K.
# Sorting by Euclidean distance

(Asked by: username_0 on 2011-10-24)

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

**Tags:** cg.comp-geom, sorting
> **Comments:**
> **username_1**: You can consider a grid of appropriate size and group points by corresponding square (using, say, hash table). Then for certain pairs of squares you can infer that all points from one square are farther from $x$ than all points from another square. In practice it could help, I guess.  
> **username_2**: The “no-brain approach” which you stated runs in O(n log n) time, where n is the number of points in S, which I guess is pretty fast in practice.  Do you want to shove off the log n factor, or do you want something else such as [external sorting](http://en.wikipedia.org/wiki/External_sorting)?  
> **username_0**: The point is that I have practically unlimited time to prepare my set of points, but the time to sort them is very much limited. That said, any speed-up of standard sorting is appreciated - even if it is same O(n log n), but faster in worst case (or best case, or whatever).  
> **username_0**: For example, if I store S as a 2-d-tree, I can find one nearest neighbour in O(log n) time. Maybe there is a similar solution for my task. I'm not a great expert in spatial data structures - and there is so many of them - I could easily miss it.  

---

## 2 answers

### Answer by username_4 on 2011-10-24. Score: 13 | Accepted answer

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](http://en.wikipedia.org/wiki/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)$.

> **Comments:**
> **username_4**: PS here's an alternative variant of solution 2 that uses the same space and query time but trades off a more complicated preprocessing algorithm for a simpler query algorithm: http://11011110.livejournal.com/233793.html  
> **username_6**: Why do $n^4$ pre-processing when you could sort from all $n$ starting points in $O(n^2\log n)$ time and store the results in a hash table using space $O(n^2)$ for constant lookup?  
> **username_4**: Because there are $\Theta(n^4)$ starting points with different sort orders, not $\Theta(n^2)$.  

---

### Answer by username_3 on 2011-10-24. Score: 1

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.

> **Comments:**
> **username_4**: If one partitions the plane into regions with different sort orders, there are $\Theta(n^4)$ regions, not $O(n!)$. The boundaries between regions are the perpendicular bisector lines of pairs of points, there are $\Theta(n^2)$ such lines, and the set of regions is given by the arrangement of these lines.  
> **username_5**: @David I think you should make this an answer.  
> **username_3**: Seconded - n! felt wrong as I was writing it, but I couldn't see a case against.  I'll amend my answer shortly to correct that, but I'd really like to see a more directly-informed one; thank you!  

---

