Efficient algorithm for calculating distance between a community (interconnected nodes) to another point

Question

I have a graph structure in a spatial domain (say a dense community like structure) and a query point. I want to devise efficient algorithms + Data Structures to calculate distance between this group as a whole and the query point.

A suitable distance function here could be averaging the distance of all points from the query point. An alternative function could be taking the maximum of all distances.

How should I go about this problem?

Answer 1

If spatial distances: I would suggest root-mean-square distance, which, unlike centroid, is in the spirit of your two suggestions in that it is a function of the distances from the query point to each point in the community. Preprocess the community by summing, for each point (x, y), the distance squared polynomial (X - x)^2 + (Y - y)^2 in variable X and Y. Then compute the RMS distance by plugging in the query point, dividing by the number of community points, and taking the square root.