Dave,
This sounds a bit like quibling. Nearly all computational geometry
algorithms assume real coordinates. Floating point implementation is
a separate problem. This is _algorithm_ geeks... ;-)
Nonetheless, if the coordinates are rational, then you can choose
A,B,C integer as I said. Exact
Hi guys. I still think you can do it in O(n^2) if you grant that a
hash table is O(1). For each pair of points (there are n(n-1)/2 of
them, which is O(n^2), find A, B and C such that
,
Ax + By + C = 0
and furthermore ensure that A^2 + B^2 = 1. (Alternately if you are
using rational arithmetic,
@Gene: The problem is that the quantities A, B, and C are likely to be
floating point numbers because the x and y coordinates of the points
are floating point numbers. You probably are going to want to compare
for equality to within a tolerance. You can do that if you sort the
slopes, but how do
@Ravindra: Can you explain the algorithm for step 3 in more detail? I
don't yet see how you do it in O(n^2), since it seems to me that
comparing one A[i,j] to all the A[j,k] is already O(n^2). What am I
missing?
Dave
On Oct 24, 12:05 am, ravindra patel ravindra.it...@gmail.com wrote:
Can be
We can do the following in 2-D plane where the pints are given in the
form of (x.y).
For each selection of three points do the following:
Find the area of the triangle of the three points. Let it be A.
If A is zero then Print Existence of Co-linear points Break.
This can be achieved in C(n,3)
for the 3th step,
for i=1 to n
for j=i+1 to n
for k=j+1 to n
compare A[i,j] and A[j,k]
if A[i,j]==A[j,k]
find i,j,k are collinear.
so we should need O(n^3), is it right?
On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel ravindra.it...@gmail.comwrote:
Can be done in O(n^2) time
@Dave
I was wrong. It can't be done in O(n^2) time. The best we can do is sort
each row like you suggested in your other post. That will still be
O((n^2)logn).
Thanks,
- Ravindra
On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan mengyan.fu...@gmail.com wrote:
for the 3th step,
for i=1 to n
for
I gave an O(n^2 log n) algorithm to find the maximal number of
collinear points in a set is given in
http://groups.google.com/group/algogeeks/msg/d329dda12b332dd1.
A fairly simple modification could answer the question as to whether
any three points are collinear.
Dave
On Oct 23, 6:31 pm, Meng
Thank you!
By the way, to do the 'sort s(i+1:n)', if I use counting sort, I think it
should be better.
imax = 0 // location of longest string of duplicate slopes
lmax = 0 // length of longest string of duplicate slopes
smax =
@Meng Yan: s is an array of real numbers, not integers, so perhaps a
counting sort is not applicable.
Dave
On Oct 23, 10:51 pm, Meng Yan mengyan.fu...@gmail.com wrote:
Thank you!
By the way, to do the 'sort s(i+1:n)', if I use counting sort, I think it
should be better.
@Preetika: Then you have to look for duplicates in an array of n(n-1)/
2 real numbers. I think this takes the complexity above O(n^2).
Dave
On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote:
You have to scan every pair of points only once to get the value of 'm' and
'a', so the
Can be done in O(n^2) time using the slope as people suggested above.
1- Sort the points in increasing order of x cord. O(nlogn)
2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) -
O(n^2) [Note that point i and j are sorted in increasing order of x]
3- find a pair of A[i,j]
For duplicates, either we can sort or use a Hash Set at the cost of extra
space. While traversing all the points for slope etc calculation, insert the
point into hash set. If a point already exists, skip it. Like this, we are
calculating the slope and keeping track of distinct points in a single
13 matches
Mail list logo
