ac
BAN USERnewbie
hey abhinav, circumcenter will give you the point equidistant from the three starting points, no reason it will minimise the sum of distances... in fact an easy counterexample can be constructed using a *very* obtuse isosceles triangle
in any case, as Anonymous has commented, manhattan metric is the likely choice here as a mention of grid is made
Assumption: all the members of the array are unique -- this is just for simplifying the explanation, removable with no new idea involved
the idea is to look at the 4-SUM as a 1+3-SUM problem
step 1) sort the array - n log n
step 2) for every element a in the array, find if there exists triplet (b,c,d) with sum S-a
so we get the newer problem of checking for 3-SUM in an array, this is already answered in on this forum, can be done in n^2 log n, and it is the exact same reduction. look at this as 1+2-SUM problem
step 1) for every element a
step2) find a pair (b,c) such that b+c = S-a
and so on... can be generalized for any k-SUM with complexity n^(k-1) log n
i am hoping this can be done faster
hi simon, this is a very specific case of the stiener tree problem which is NP-hard. in that prblem in stead of choosing just one point, you get to choose more (and thus the complexity)
- ac September 06, 2012here we just need to choose one vertex, so its a stiener-star of sorts and as anonymous has commented on top, for euclidean metric, its just a convex program that can be solved efficiently and up to any desired precision