Author |
Topic: Non-collinearity of Points (Read 1183 times) |
|
Terps.Go
Newbie
Gender: 
Posts: 13
|
 |
Non-collinearity of Points
« on: Jan 24th, 2005, 9:14am » |
 Quote  Modify
|
The input is a set S of n points in the plane in general position (no 3 points lie on a line). Derive an O(nlogn) worst-case time algorithm to construct a new point X such that X is not collinear with any pair of points in S.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-collinearity of Points
« Reply #1 on: Jan 24th, 2005, 4:38pm » |
Quote Modify
|
Nice problem Terps.Go!
I am pretty sure, a simpler solution would exist.
Here is the algorithm (hidden, highlight to view)
We do the following first. We consider the geometric dual of the set of points. In the dual, our points are mapped to lines such that no two lines are parallel and no three concurrent.
Note that the conversion to the dual can be done in O(n) time. (Consider a circle and take the polars(/poles?) of the points wrt the circle. I think the process is called inversion).
The problem now becomes:
Given a set of n lines in general position in a plane, find a line L which does not pass through any of the points formed by the intersections of the n given lines.
Now given a set of n lines, we can compute the Convex Hull of their intersection points in O(nlogn) time.
(
Reference: Atallah, M.J.,
Computing The Convex Hull Of Line Intersections,
J. ALGORITHMS(7), 1986, pp. 285-288
)
It is clear that the size of the convex hull is no more than 2n, as each line contributes at most 2 points to the convex hull.
All we need to do is find a line not passing through the convex hull and we are done. This can be done very easily by finding the min x-coordinate (say m) of the vertices of the hull and choosing the line x = m - 1000 to be our line. This can be done in O(n) time as we need to consider at most 2n points.
Now we convert this line back to a point in our original plane.
Thus we have an O(nlogn) algorithm.
Note that we didn't actually need to compute the whole convex hull, this leads me to believe there might be an O(n) algorithm for this. Maybe we could extract something from the details of Atallah's algorithm.
:::
|
|
IP Logged |
|
|
|
Terps.Go
Newbie
Gender:
Posts: 13
|
|
Re: Non-collinearity of Points
« Reply #2 on: Jan 24th, 2005, 7:03pm » |
Quote Modify
|
Yeah, there is a much simpler solution 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-collinearity of Points
« Reply #3 on: Jan 25th, 2005, 5:42am » |
Quote Modify
|
I think an O(n) algorithm exists for this!
The following might work:
We consider the geometric dual. (as in the previous O(nlogn) solution)
So given n lines, no three concurrent, no two parallel, we need to find a line which does not intersect the convex hull of the points of intersections of the lines.
It will be enough if we could find two line segments which lie along two sides of the convex hull. Extending the two lines, we can divide the plane in two regions, one which does not contain the convex hull. It is now easy to find the required line.
In order to find a side, the following seems to work.
(useful to draw a figure)
Consider three lines L1,L2,L3. Say they intersect in A,B,C with B and C on L3. Now consider the region R formed by L1, L2 which contains B and C. segment BC, L1 and L2 are the boundaries of that region. We keep track of points of intersection of L1 with other lines (say X) which is furthest from A and in the region R. Similarly we maintain a point Y for L2. (Initially X = B, Y = C). As we consider each of the lines L4,L5,...,Ln in order, X or Y or both, change. After we have looked at all the lines, the final values of X and Y will lie along one side of the convex hull! (Seems true, haven't tried proving it yet)
The above process can be done in O(n) time.
:::
So it looks like we might have an O(n) time algorithm.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-collinearity of Points
« Reply #4 on: Jan 25th, 2005, 6:10am » |
Quote Modify
|
Aryabhatta, your idea is absolutely brilliant! I like it a lot. 
The dual transformation you described is called reciprocation, and it's based on inversion.
When practically using this idea, we need to be careful though: If the center of the circle is chosen to be collinear with any pair of given points, then the image will contain parallel lines. How do you treat them? Does the source you gave in the previous post consider this?
So, we would better choose the center of the circle to be collinear with any pair of points - a vicious circle... 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-collinearity of Points
« Reply #5 on: Jan 25th, 2005, 11:16am » |
Quote Modify
|
on Jan 25th, 2005, 6:10am, Barukh wrote:
When practically using this idea, we need to be careful though: If the center of the circle is chosen to be collinear with any pair of given points, then the image will contain parallel lines. How do you treat them? Does the source you gave in the previous post consider this?
So, we would better choose the center of the circle to be collinear with any pair of points - a vicious circle... |
|
Thanks for clarifying that, I was wondering what happens to parallel lines when we transform back!
We definitely can choose the center of the 'reciprocating' circle such that at least 3 (or any constant for that matter) lines are in general position and such that no lines are parallel to any of those 3 lines.
Once we do that, I don't know about the O(nlogn) solution. I would have to read that paper to find out if it considers the case if 2 lines happen to be parallel. (I would think it would).
The O(n) 'solution' needs to find the side of the convex hull even if lines are parallel (with none parallel to the 3 special lines). All we need is a proof! Which I am not sure of now, even with the no two parallel restriction...
To find a line (required in both solutions) not parallel to any of the existing lines, we just need to pick a line of <min or >max slope lying entirely in the region not containing the convex hull. I don't think that should be too much of a problem.
So I think the O(nlogn) solution would work (dependent on Atallah's algo) but the O(n) might not work without modifications.
[EDIT1]
OK. I think the O(nlogn) algorithm is definitely salvagable, even if Atallah's algorithm does not cater to parallel lines.
We do the same thing: convert the points to lines using a reciprocating circle.
Now we get a set of n lines, whose convex hull needs to be found.
Sort the lines by their slope. Notice that any slope will repeat at most _twice_ as we are given that no three input points are collinear.
Thus we can split the n lines into two sets S1 and S2, such that lines in S1 are in general postion and lines in S2 are in general position. Run Atallah's algorithm on both these sets independently to get two convex polygons. Note that the number of vertices in both these polygons is O(n).
Now there is a standard O(n) time algorithm to find the convex hull of two given convex polygons each of size O(n). (That method is used in the divide and conquer method of finding convex hulls).
Thus we have an O(nlogn) time algorithm.
[/EDIT1]
It looks like the O(n) time algorithm might also be salvagable. Will edit this post...
|
| « Last Edit: Jan 25th, 2005, 12:13pm by Aryabhatta » |
IP Logged |
|
|
|
rdinal
Guest
|
|
Re: Non-collinearity of Points
« Reply #6 on: Jan 25th, 2005, 12:57pm » |
Quote Modify
 Remove
|
This is too complicated for me gentlemen... too... many... unfamiliar... words...
I can give you a O(N) algorithm to generate N non-collinear points starting from scratch...
|
|
IP Logged |
|
|
|
Terps.Go
Newbie
Gender:
Posts: 13
|
|
Re: Non-collinearity of Points
« Reply #7 on: Jan 26th, 2005, 7:18am » |
Quote Modify
|
Hi rdinal,
I know a O(nlogn) algorithm that is pretty simple. Let see how far people can go!
|
|
IP Logged |
|
|
|
rdinal
Guest
|
|
Re: Non-collinearity of Points
« Reply #8 on: Jan 26th, 2005, 9:48am » |
Quote Modify
Remove
|
on Jan 26th, 2005, 7:18am, Terps.Go wrote:Hi rdinal,
I know a O(nlogn) algorithm that is pretty simple. Let see how far people can go!
|
|
Terps, don't get me wrong, I have no idea how to solve your problem in O(N log(N)). All I said was that a (simpler) problem of generating N non-collinear points from scratch (you're not given any points to begin with) has a O(N) solution. But surely, that's too easy to discuss.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-collinearity of Points
« Reply #9 on: Jan 27th, 2005, 2:05am » |
Quote Modify
|
Here’s another approach that might work.
Let the points have coordinates (x1, y1), …, (xn, yn).
1. Sort all the x-coordinates (in any order), and find xMIN, xMAX.
2. Working on the sorted array, find dxMIN – the minimal non-zero difference between 2 consecutive elements.
3. Find yMIN, yMAX from the y-coordinates.
4. Compute SMAX = (yMAX - yMIN)/ dxMIN.
Surely, all this may be done in O(n log(n)) time. Now, SMAX is the upper bound of the slopes of all the existing lines except lines parallel to y-axis (for which the slope is infinite). If we now choose the point (X, Y) such that it will make with any given point a line with a finite slope bigger than SMAX, then surely it cannot be collinear with any pair of given points. Take X, Y to satisfy the conditions: X > xMAX, (Y- yMIN) > (X- xMAX) * SMAX, and we are done.
I would like other to comment on this.
|
| « Last Edit: Jan 27th, 2005, 2:08am by Barukh » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-collinearity of Points
« Reply #10 on: Jan 28th, 2005, 12:20am » |
Quote Modify
|
on Jan 27th, 2005, 2:05am, Barukh wrote:1. Sort all the x-coordinates (in any order), and find xMIN, xMAX.
2. Working on the sorted array, find dxMIN – the minimal non-zero difference between 2 consecutive elements.
3. Find yMIN, yMAX from the y-coordinates.
4. Compute SMAX = (yMAX - yMIN)/ dxMIN.
Take X, Y to satisfy the conditions: X > xMAX, (Y- yMIN) > (X- xMAX) * SMAX, and we are done.
I would like other to comment on this.
|
|
Let us consider a point (x,y) and see what slope the line with (X,Y) makes.
X-x [ge] X - xmax
and Y - y [le] Y - ymin
if Y > y and X > xmax we have
S = (Y-y)/(X-x) [le] (Y - ymin)/(X - xmax)
You have selected X and Y so that the RHS [ge] Smax. That does not prove S [ge] Smax
But I guess, we could choose (X,Y) so that 0 < (Y - ymin)/(X - xmax) < Smin.
Where Smin is the least positive slope and X > xmax and Y > ymax.
We need the following to be true:
ymax < Y < Smin(X-xmax) + ymin and X > xmax.
Choosing a large X > xmax should do the trick.
Finding a lower bound for Smin and using that instead should be no problem I think.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-collinearity of Points
« Reply #11 on: Jan 28th, 2005, 4:46am » |
Quote Modify
|
I felt something was wrong with that. Thanks, Aryabhatta, for pointing. I don't understand what I thought when writing this last inequality. It should be this way:
(Y- yMAX) / (X- xMIN) > SMAX,
and then - following your argument - for any point (x,y),
S = (Y-y)/(X-x) [ge] (Y-yMAX) / (X-x) [ge] (Y-yMAX) / (X- xMIN) > SMAX
Is it OK?
|
| « Last Edit: Jan 28th, 2005, 4:47am by Barukh » |
IP Logged |
|
|
|
rdinal
Guest
|
|
Re: Non-collinearity of Points
« Reply #12 on: Jan 28th, 2005, 3:40pm » |
Quote Modify
Remove
|
Barukh, I see no fault in your solution.
It looks though that as you add more points, your Y-coordinate will grow exponentially, which may not be desirable... At the same time X can stay the same (=Xmax). Anyway, I don't see how this can be fixed.
|
|
IP Logged |
|
|
|
rdinal
Guest
|
|
Re: Non-collinearity of Points
« Reply #13 on: Jan 28th, 2005, 5:15pm » |
Quote Modify
Remove
|
on Jan 28th, 2005, 3:40pm, rdinal wrote:| At the same time X can stay the same (=Xmax). |
|
That, of course, was wrong...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-collinearity of Points
« Reply #14 on: Feb 1st, 2005, 3:26pm » |
Quote Modify
|
on Jan 28th, 2005, 4:46am, Barukh wrote:I felt something was wrong with that. Thanks, Aryabhatta, for pointing. I don't understand what I thought when writing this last inequality. It should be this way:
(Y- yMAX) / (X- xMIN) > SMAX,
and then - following your argument - for any point (x,y),
S = (Y-y)/(X-x) [ge] (Y-yMAX) / (X-x) [ge] (Y-yMAX) / (X- xMIN) > SMAX
Is it OK?
|
|
It looks fine to me.
I haven't gotten time to get to trying for the O(n) solution.
The idea seems promising and the O(n) algo seems so close...
Did anyone make any progress?
|
| « Last Edit: Feb 1st, 2005, 3:28pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print