w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
How to find a "central" anchor-point in a point-set/2D-shape?

here is solution that can find the green point in O(N) :-

Find mean (xm,ym)

Suppose (xm+a),(ym+b) is a point in the dataset

E(xi,yi) = sum of squared distances of all points from (xi,yi)

E(xm,ym) = k   because it is the mean.

E(xm+a,ym+b) = summation => (xi-(xm+a))^2 + (yi-(ym+b))^2

             = summation => ((xi-xm)-a)^2 + ((yi-ym)-b)^2

             = summation => (xi-xm)^2 + (yi-ym)^2 + a^2 + b^2 -
2a*(xi-xm) - 2b*(yi-ym)

             = summation => (xi-xm)^2 + (yi-ym)^2 + summation => a^2
+ b^2 +.....

   summation => (xi-xm)^2 + (yi-ym)^2 = E(xm,ym) = k

Hence

E(a,b) = summation => a^2 + b^2 - 2a*(xi-xm) - 2b*(yi-ym)

as a,b are constant in summation

E(a,b) = (a^2+b^2)*N - 2a*(summation=>(xi-xm)) -
2b*(summation=>(yi-ym))

summation=>(xi-xm) = 0
summation=>(y1-ym) = 0

E(a,b) = a^2 + b^2

Now to get green point which will minimize E(a,b)

a = xk-xm
b = yk-ym 

find (xp,yp)=>minimum{E(a,b)}  among all (xk,yk)

summation=>(xi-xm) and summation=>(yi-ym) can be found in O(N) after
finding mean

hence E(a,b) can be found in O(1) and (xp,yp) in O(N) 




© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.