17
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ilyaraz Oct 24 '11 at 15:03
  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Oct 24 '11 at 15:36
  • $\begingroup$ 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). $\endgroup$ – Alex K. Oct 24 '11 at 17:38
  • $\begingroup$ 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. $\endgroup$ – Alex K. Oct 24 '11 at 17:40
13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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: 11011110.livejournal.com/233793.html $\endgroup$ – David Eppstein Oct 25 '11 at 23:22
  • $\begingroup$ 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? $\endgroup$ – Dave Oct 26 '11 at 14:19
  • $\begingroup$ Because there are $\Theta(n^4)$ starting points with different sort orders, not $\Theta(n^2)$. $\endgroup$ – David Eppstein Oct 26 '11 at 14:41
1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 24 '11 at 22:13
  • $\begingroup$ @David I think you should make this an answer. $\endgroup$ – James King Oct 24 '11 at 22:42
  • $\begingroup$ 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! $\endgroup$ – Steven Stadnicki Oct 24 '11 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.