Author |
Topic: Closest Point (Read 8341 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Closest Point
« on: Mar 11th, 2003, 4:34pm » |
 Quote  Modify
|
You are given coordinates for a set of N points on a 2D plane. After preprocessing those points in some manner of your own discretion, you are given a new point v = (x,y). Now your task is to determine which of the original N points is closest in Euclidean distance to v. Devise the best algorithm (lowest big-Oh runtime) you can to accomplish this task.
Note 1: From a tech-interview. Contributor: Anwis Das, a colleague of mine.
Note 2: Exactly how much time you can spend preprocessing is not specified, but I think it's reasonable to say it shouldn't be exponential. After preprocessing, the interviewer did give a runtime that your algorithm should meet for determining the point closest to v. However, I won't give that away, because it could be too much of a hint; furthermore, I am uncertain if an even better runtime does not exist.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Closest Point
« Reply #1 on: Mar 19th, 2003, 3:51am » |
Quote Modify
|
I've got a solution that runs in O(N), but it seems much too obvious. On the other hand, you can easily reduce the well-known least element problem to this one, and that problem is OMEGA(N), which theoretically shows that there is no possible improvement - I have some misgivings because, to reduce that problem to this one, you must know in advance a lower bound on the element of the sets, which possibly eliminates the OMEGA(N) property. What puzzles me is the preprocessing thing, which my solution does none of. Any other ideas?
My solution:
* store all the points in some convenient data structure
* once given v = (x,y), subtract this point from all the others
* for every resulting point, calculate the sum of the squares of its x- and y-components
* find the least of these, and that will be the closest point
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Closest Point
« Reply #2 on: Mar 19th, 2003, 7:32pm » |
Quote Modify
|
In the preprocessing, figure out the polygons around each of the N points such there is exactly one of the N points within each polygon and every location within the polygon is closest to the point. I think these are called Voronoi polygons. Also find the convex hull of the points and the smallest circle that completely encloses all of the finite Voronoi polygons. Chop up this circle, or use the circumscribing square, into a bunch of small pixels. A more efficient means of having variable size pixels would work better but for simplicity I'll assume all pixels are the same size. Paint each Voronoi polygon with a flood fill such that instead of a color, each pixel has data giving a list of all the N points that could possibly be closest to a spot within that pixel. If the pixels are small enough, most pixels will be completely enclosed within a Veronoi polygon, some will fall on the border of two polygons, and a some will have more. For the infinite radial edges of the outer polygons (which lie outside the patch of pixels) find the angle of the rays that go outward from the surrounding circle and sort in order.
Given a point, it can be immediately computed which pixel it lies within or whether it lies outside the surrounding circle. If it lies in a pixel there will be a very short list (probably less than 3) of points from the orginal set to check for closest. If outside the circle, find polar angle from center of circle and use binary search to find which two points on perimeter of convex hull this could possibly be closest to. Will need a little more complexity on the convex hull calculation in case 3 or more colinear points lie on it.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Closest Point
« Reply #3 on: Mar 20th, 2003, 12:21pm » |
Quote Modify
|
SWF,
I don't think your idea guarantees O(1) performance, because there's no guarantee that any fixed-size area in the plane will have O(1) voronoi polygons in it. Consider the case where the original N points are in a circle. One pixel in the middle may touch all N points, in which case your solution is O(N) in the worst case.
Therefore, you will have to fit the point V into boundaries based on the locations and sizes of the voronoi polygons (rather than into a fixed grid).
Here's my idea for pre-processing, although it's not entirely fleshed-out at the moment.
The idea is to end up with a binary tree structure. You'll look up the point V in the tree, going from the root to the leaves. Each step will have a criterion on the coordinates of the point V (for instance a straight line that splits the plane in two). For V on one side of the line, you go down the left branch, and on the other side, you go down the right branch. Because this is a binary tree, you should be able to look up a point in O(log(N)) time.
Keep in mind, however, that any straight line you draw for a criterion will, in general, pass through some of the voronoi polygons. This means that there will always be some points that end up on both sides of the line. This creates some difficulty in choosing the line and creating a tree; If too many points end up on both sides of the line, then you may not get O(log(N)) performance.
So how can we ensure the tree will give O(log(N)) performance? We must be able to pick a line so that at least O(N) points do not lie on the line (so to speak--it's actually the points' voronoi polygons that we care about). These points must be divided roughly evenly between the two sides. Can we always do this? I believe that we can, but I haven't proven it.
Having thought more about it, I think we can't do it with only lines (ie. I came up with a pathological case). We may also need to use circles or other simple geometric shapes. However, I am sure that with fixed-complexity boundaries, we can always divide the points into three groups:
A = {points with veronoi polygons completely on the positive side of the boundary}
B = {points with veronoi polygons completely on the negative side of the boundary}
C = {points with veronoi polygons dissected by the boundary}
Note that the size of set A is O(N) and the size of set B is O(N).
For the next level, we decide on more lines to break up the sets (A U C) and (B U C). Even when we have a small number of points to break up, we can always choose a line so that A is non-empty and B is non-empty (by choosing a line on the boundary of two voronoi polygons).
Now the only difficult task is to show that we can always choose a fixed-complexity boundary to divide the points up like this, and hopefully to show how we can choose it. Hmm...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Closest Point
« Reply #4 on: Mar 24th, 2003, 6:05pm » |
Quote Modify
|
Does big-Oh run time mean worst case, mean, or something else? I thought Quicksort is not considered O(N^2).
The case of picking a the pixel with all N Voronoi polygons would be pretty unusual. Could define pixels so none contains more than one point with more than 2 Voronoi polygons meeting. Then sort the angular location of the surrounding points. When this pixel is chosen, much like when a point is chosen outside the convex hull, use a binary search to quickly narrow down the candidate closest points.
For James' approach of cutting the points into half, how about using the boundaries of the Voronoi polygons? Dermining which side of the path you are on is more time consuming than for a single line, but makes the other issues easy to deal with.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Closest Point
« Reply #5 on: Mar 26th, 2003, 10:45am » |
Quote Modify
|
SWF,
I did think about using the boundaries of the Voronoi polygons as the lines, but the problem is that to divide them into two regions (each of O(N) size), you must use more than one boundary line (think of a hexagonal grid of polygons--you need a zig-zag). This boundary line could be O(N) complexity in worst case, meaning that it could take you O(N) time to decide which side V is on. Perhaps we can guarantee that there is some boundary line that isn't O(N) in complexity, but I couldn't see how to do it. Even if we can do better than O(N), we probably can't beat O(sqrt(N)).
As for the O(N) notation, I think you have to specify whether it's average-case or worst-case. I assumed worst-case, but if not, then the pixel solution stands as O(1), which is pretty good!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Googler
Guest
|
It seems that no matter what, the entire list of n points need to be cycled through once to determine the closest point to V, so the best running time would be Omega(n). But my solution seems a little too obvious, so I must be missing something, but here's my algorithm:
1. Go through the entire list of n points, given any point p(Xp,Yp), calculate the distance between p and v [or better yet, just calculate (Xp-Xv) + (Yp-Yv). This is not the "actual" distance between the two points, but should be good enough of a "gauge" to determine how far the two points are, and it doesn't involve taking the square or square root of anything].
2. Keep a running minimal distance between any of the points and V, compare the new distance calculated to the known least distance. If the new point is closer, use the new point as the new min.
3. After the entire list has been run through, return the point that holds the minimum distance to V out of all n points.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Closest Point
« Reply #7 on: Apr 17th, 2003, 7:25pm » |
Quote Modify
|
Googler, the point your are missing is the pre-processing. The point of that is to do some calculations in advance to save time later, by avoiding doing your proposed algorithms. Some of the methods given above are better than O(N).
|
|
IP Logged |
|
|
|
Papa Homer
Guest
|
I propose a solution that runs in O(4logN). First, some notation:
S : original set of points
N : size of S
v : "query" point
Second, let's state the obvious. The upper bound for this problem is O(N) since that is the time it takes to compute the distance from v to every point in S. Keeping track of the minimum distance calculated so far eliminates the need for any additional search. On the other end, the lower bound is O(logN) since that is the optimal performance for solving this problem in 1 dimension (all points on a single line).
Now, the solution. Some of the posts have refered to Voronoi polygons. Although I am not familiar with the term, based on the description I beleive that is essentially what I used in my solution. The idea is to partition the plane in the following manner. For every pair of points (p1, p2) in S, draw a line bisecting the segment (p1, p2) at the right angle. Clearly, every point on such a line will be at an equal distance from p1 and p2. We will truncate these lines whenever they intersect, thus partitioning the plane into a set of open and closed polygons with a single point from S within each polygon. For any point v, the closest point in S will be the one that is within the same polygon. If v is on a polygin edge, then it is at an equal distance from 2 points in S. If v is on a polygon vertex then it is at an equal distance from 3 or more points in S.
For a set of N points there will be (N choose 2)=N(N-1)/2 pairs of points and terefore the same number of lines. Let us call tis number Q. Since we truncate the lines whenever they intersect, their are at most as many polygon vertices as their are lines (at most 2 end points for every truncated line but every vertex is shared by at least 2 lines).
Without loss of generality*, assume that no two points in S have the same y-coordinate. In other words, there are no vertical lines. We now sort this set of vertices by their x-coordinates. Imagine a vertical line passing trough every vertex, partitioning the plane into columns. Because of the sorting order, the column between any two consecutive vertices does not contain any vertices. In other words, the polygon edges do not intersect within that column, forming (irregular) rows. For every column, we will keep the polygon edges present in that column sorted by their vertical ordering.
In order to find the point closest to v in S, we perform two searches. First, we find the column that contains v. This is a simple O(logQ) = O(logN2) = O(2logN) search. Then we have to find the row. Once again a simple O(logQ) = O(logN2) = O(2logN) search (a binary search of the polygon edges present in the column, checking which side of the edge v falls on). The total runtime is O(4logN). However, the actual performance should be significantly better. In order to simplify the analysis of the algorithm, I have made some simplifcations that negatively effect the perfromance. For example, the number of polygon edges in any column should be much less than the total number of lines, thus speeding up the row search.
* If there are points in S with the same y-coordinate, then we can rotate the set (and later v) around an arbitrary point until that is no longer the case. In any case, this assumption was made just to make the analysis simpler by making it possible to divide the plane into rows and columns. Their are simpler ways of dealing with such cases in practice.
|
|
IP Logged |
|
|
|
BehemothCat
Newbie
Posts: 3
|
|
Re: Closest Point
« Reply #9 on: Apr 25th, 2003, 3:55pm » |
Quote Modify
|
Here’s an elegant, but hard to explain solution that’s approximately O(sqrt(N)).
Start by building the Voronoi polygons (nice tip, SWF!).
V is the total vertex count.
N is the polygon count (same as the original Point count).
Assign each polygon an arbitrary ID value from 1 to N.
Assign each vertex an arbitrary ID value from 1 to V.
Then build a tree like structure incorporating the Voronoi polygon vertices. I say tree like, but a corkscrew willow is probably the closest analogy. The tree structure mirrors the structure of the Voronoi polygons. There are V nodes, each of which has the coordinates of its associated vertex, along with n branches where n equals the number of lines intersecting at this vertex (typically 3). Each branch points to a child node which represents the vertex at the other end of one of the lines intersecting at this vertex. Additionally, each node has a polygon ID associated with each of it’s branches (if there are 4 branches, then there are 4 polygon IDs). The polygon ID for each branch is the ID for the polygon to the “right” of each branch (imagine yourself standing on a vertex and rotating in a circle – it becomes clear which polygon ID goes with which branch). It helps if the branches are ordered in a clockwise order (starting point doesn’t matter, but order does).
Note that every branch is a two-way arrow – every child node has a node that points back to it’s parent. Note also that there are no leaves (dead ends) in the structure.
Now that we are finished with the preprocessing, let’s use the structure to find a closest point.
Variables used to help us find the point:
StartVID – vertex ID of the starting point of the tour of the polygon we are currently touring
PID – ID of the polygon we are currently touring
PreviousVID – ID of the parent node (vertex)
We can enter the structure at any node, but it’s most efficient to enter at a preselected node that is centrally located.
First Node:
Having entered the structure, we cycle through the branches to determine which two branches “contain” our point (which two lines define an angle encompassing our point – I’m glossing over some details here). We will be traversing the structure using the “leftmost” of the two branches. Before we do, we first set StartVID and PreviousVID to be the vertex ID of the entry node. Set PID to 0 (invalid ID). Now we traverse to the second node.
Second Node:
We again determine which two branches “contain” our point as well as which one is the “left” branch. If the “left” branch is immediately counter-clockwise of the PreviousVID branch, then StartVID is unchanged. Otherwise, set StartVID to be the vertex ID of the current node. We now set PID to be the polygon ID of the polygon associated with the branch we are just about to traverse (the polygon to the “right” of the branch). We also change PreviousVID to be the vertex ID of the current node. Now we traverse to the next node.
All Subsequent Nodes:
We again find our “left” branch. If the “left” branch is immediately counter-clockwise of the PreviousVID branch, check to see if the vertex ID of the current node is equal to the StartVID. If they are equal, we are done and the closest point is the point associated with polygon PID! If the “left” branch is NOT immediately counter-clockwise of the PreviousVID branch, then we set StartVID to be the vertex ID of the current node and also set PID to be the polygon ID of the polygon associated with the branch we are just about to traverse. If we aren’t done, then we change PreviousVID to be the vertex ID of the current node and then traverse to the next node.
Basically, what we are doing with this algorithm is homing in on the Voronoi polygon that contains our point and, when we reach it, we tour it’s vertices in clockwise fashion until we have completely traversed the polygon.
Ack – such a long post. Hope it’s not too confusing.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Closest Point
« Reply #10 on: May 1st, 2003, 2:09pm » |
Quote Modify
|
Papa Homer,
Good work on the vertical-line solution! That's a very good way of doing it. I guess what you've identified is that for a convex area with no vertices in it, it's always easy to sort out where a point lies. You just do a binary search comparing the point with the various voronoi edges.
I have a couple of nits to pick though. First, it doesn't seem to matter to me if two vertices are both on the same line. You will still be able to do a simple binary search through the column. In fact, if two are on the same line, you get the advantage of one fewer columns. This is good!
So maybe we can speed things up (algorithmically) by doing the following: instead of choosing vertical lines, we choose lines in any direction, so that the lines always pass through two vertices. Each line we choose will have the same number of vertices on both sides. We can then split up the vertices in a binary-tree fashion, until we have sorted the point V into a convex space that has no vertices inside it (just some vertices on the edges). Now we can do our search through that space.
However, doing the time analysis on this modification, it only saves you a couple of steps in the search tree, so you're looking at probably an additive time reduction O(1), which is relatively insignficant. We can get a multiplicative time reduction (reduce the factor in front of the log(N)) if we either eliminate one of the two steps (sorting into regions, then sorting inside the regions), reduce the order of either of these operations, or just make our implementation faster.
But really, it's a great solution--wish I'd though of it!
BehemothCat,
As for the tree-walk solution, that's not guaranteed to be any better than O(N) as far as I can tell. I certainly considered something like that, but you don't have any control over the structure of the tree, so you can't make any promises about running time. If you choose a different structure, you might be able to do it, but I have a feeling it will be messy--much like my solution was.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Papa Homer
Guest
|
Thanks. The reason I avoided multiple vertices on a line is because I was worried about the possibility that all original points (or a large fraction of them) lie on the same line. That would result in linear search time. It's ok to allow more than 1 vertex on a line as long as the number is bound by a constant not related to N. Also, one of the advantages of using horizontal and vertical lines is that it is very efficient to check which side a point falls on (a single integer comparison).
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Closest Point
« Reply #12 on: May 7th, 2003, 12:51pm » |
Quote Modify
|
Papa Homer,
I'm still trying to visualize all the voronoi vertices existing in a straight line, and the best I come up with is that all original points lie in two straight parallel lines, evenly spaced. I don't see how this creates O(N) search time, because as long as you can find any convex region that contains no voronoi vertices, you can always do a binary search on the edges within that region. We know that the number of edges must always be bounded by n2 (number of points choose 2), and when you take the logarithm, the square just becomes a multiplicative factor.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove