Algorithm to find optimal point coordinates Let's allow that there is a matrix of approachibilities of the NN size (N >= 500), a matrix of costs of NM and K of points with coordinates (x1, y1), (x2, y2)..., (xk, yk)
In a matrix of costs movement cost from a point of I (by xi, yi) in J point (xj, yj) is described. Thus cost is a tupple of two elements: tij - time for moving from i point to j and dij - distance between i and j points. If time is equal, it is necessary to take a point to which the distance is the smallest.
There are K of points (P1, P2, P3, P4). It is necessary to find such a point X which cost would be minimum.
The K is much smaller than N, M

 A: My first idea would be some kind of parallel Dijkstra: A node in the priority queue would be a tuple denoting a point and the identity of one of the k target points. So you'd visit each point up to k times. The priority queue would expand nodes ordered by cost (or time, whatever you choode there), without regard for the associated target node. When you visit a node which has already been visited from all the other k − 1 targets, then it has a chance to be the point x you are looking for.
If the final cost for x simply is the maximum of the k scores to the individual targets, then this will be the point you're looking for, as any point encountered later in the priority queue will have at least that maximum cost. If you want the sum to be minimal, you might have to go until costs popped from the priority queue reach k the sum of your current best candidate for node x.
If there is some relation between the geometric location of your points and the costs between these points, then perhaps you can use A* to explore your graph in a directed fashion, concentrating towards the location where some heuristic predicts the solution to be. So if there is any such relation between cost and distance, you might want to give more details on that.
A: I think this can be solved in $O(\max(N,M))$ time and $O(\max(N,M))$ space.
We have to find the median of $x$ coordinates and median of all $y$ coordinates in the $k$ points and the answer will be $(x_{median},y_{median})$;
Let the input of the coordinates be an array of coordinates.
coord_t c[k]
struct coord_t {
   int x;
   int y;
};

My idea is to create an array of size = N>M?N:M;
int array[size] = {0}; //initialize all the elements in the array to zero

for(i=0;i<k;i++)
{
   array[c[i].x] = +1;       
   count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
   if(array[i]!=0)
   {
      tempCount += array[i];
   }
if(tempCount >= count/2)
{
break;
}

int x_median = i;

//similarly with y coordinate.

int array[size] = {0} ; //initialize all the elements in the array to zero 
for(i=0;i<k;i++)
{
   array[c[i].y] = +1;       
   count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
   if(array[i]!=0)
   {
      tempCount += array[i];
   }
if(tempCount >= count/2)
{
break;
}

int y_median = i;

coord_t temp;
temp.x = x_median;
temp.y= y_median;
return temp;

