try searching "Manhattan Distance"
On Wednesday, April 25, 2012 11:10:38 AM UTC+5:30, tech coder wrote:
>
> Given N points(in 2D) with x and y coordinates. You have to find a
> point P (in N given points) such that the sum of distances from
> other(N-1) points to P is minimum.
>
> --
>
> Rega
I actually made a mistake. The function is convex and binary search works.
Look up GEOMETRIC MEDIAN in Wikipedia.
-Nima
On May 9, 2012 10:24 AM, "atul anand" wrote:
> sort p(xi,yi) on the basis of x-axis. find media of x-axis = x_median
> sort p(xi,yi) on the basis of y-axis. find media of y-ax
sort p(xi,yi) on the basis of x-axis. find media of x-axis = x_median
sort p(xi,yi) on the basis of y-axis. find media of y-axis = y_median
find distance from p(x_median,y_median) to all N points.
the distance minimum from p(x_median,y_median) is the point closest point.
algo seems to work , but
Wait! Let's clarify things before shooting random guesses.
First of all, which norm is used for distance?
I'm assuming that it is L2 norm (Euclidean distance).
The problem statement clearly mentions that the answer should be one of the
given points. So, I don't see any rationale behind taking the m
On Tue, May 1, 2012 at 8:44 PM, Bhupendra Dubey wrote:
> Find the centroid
>
> X= (x1 +x2xn)/N
> Y=(y1+y2..yn)/N
> This will precisely be the point no need to calculate and check with
> distance.
>
@dubey : Consider this case, let there be a cluster of 4 points near the
origin and 1 point
Not Necessary but for some case only
On Tue, May 1, 2012 at 8:44 PM, Bhupendra Dubey wrote:
> Find the centroid
>
> X= (x1 +x2xn)/N
> Y=(y1+y2..yn)/N
> This will precisely be the point no need to calculate and check with
> distance.
>
>
> On Tue, May 1, 2012 at 1:18 PM, mohit mishra wrote
Find the centroid
X= (x1 +x2xn)/N
Y=(y1+y2..yn)/N
This will precisely be the point no need to calculate and check with
distance.
On Tue, May 1, 2012 at 1:18 PM, mohit mishra wrote:
> Let me know if there is any bug
> /*using centroid of plane */
>
> struct point
> {
> int x;
> int y;
>
Let me know if there is any bug
/*using centroid of plane */
struct point
{
int x;
int y;
};
typedef struct point Point;
int main()
{
int n,i;
int d,dis;
float sum_x=0,sum_y=0;
Point centroid,final;
//clrcsr();
printf("how many points? ");
scanf("%d",&n);
Point p[100];
printf("enter X and Y cordi
how can we find centriod of n points in a plane?
Regards,
Santosh K.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeek
I think if we calculate the center of the graph that will give the
solution, to do that
1. find the eccentricity of every node using all pair shortest path algo's
( Floyd warshall).
2. The node which is having min eccentricity is your P.
On Wed, Apr 25, 2012 at 6:14 PM, Navneet wrote:
> We can
We can calculate the centroid of all d points and then calculate their
individual distances from it .The point with the minimum distance will
be the answer.
TC :O(n)
Regards,
PAYAL GUPTA
On 4/25/12, Navneet wrote:
> We cannot do it without computing distances of each node from all other
> nodes.
We cannot do it without computing distances of each node from all other
nodes. So to begin with, construct a matrix representation of the graph
with distances filled in for every pair of points.
Proceed to calculate the minimum spanning tree of such a weighted graph.
Kruskal's and Prim's are t
12 matches
Mail list logo
