Finding the distance from main point (hub) to the closest point

Question

I have a hub point and multiple subpoints as shown in below figure.

• How to find the closest point from main hub (P) if there are 1000 points?

• Is there a specific distance formula that gives the shortest distance from main hub to the nearest point instead of manually calculating distances for all points. I am trying to understand the maths behind it.

• For simple distance between hub and three points, the maths could be simply euclidean distance as below:

$d = \sqrt{(x_1-x_0)^2+(y_1-y_0)^2}$

Practical example: Consider we have an electric pole and we want to connect nearest houses to that pole with a given radius of 400 m. How to find the nearest houses from the pole? Is Nearest Neighbor algorithm is a good solution?

Answer 1

One main hub, many houses:

There is not really any better solution than simply calculating the distance between the main hub $(p_x, p_y)$ and each house $(h^i_x, h^i_y)$ using the Pythagorean distance formula:

$$\underset{i}{\operatorname{argmin}}\ \sqrt{(p_x - h^i_x)^2 + (p_y - h^i_y)^2}.$$

There are a few shortcuts you can take, which have no effect on the asymptotic complexity of calculating the closest house, but can reduce the work in practice:

• the minimizer of distance is also the minimizer of squared distance. So you can solve instead $$\underset{i}{\operatorname{argmin}}\ (p_x - h^i_x)^2 + (p_y - h^i_y)^2,$$ which doesn't need taking any square roots.
• the distance between the hub and a house is bounded below by $|p_x - h^i_x|$ and $|p_y - h^i_y|$. So if you already have a candidate closest house, you can check these bounds first for the remaining houses, and only compute the full distance if the house passes the quick check (rejecting those that can't possibly be closer than your existing candidate).

Many hubs, many houses:

This case is more interesting since, if you have $H$ hubs and $N$ houses, it is possible to compute the closest house to each hub in less than $O(HN)$ time. The main idea is that you precompute a geometric data structure (typically a Voronoi diagram or kd-tree) that tells you how the houses are distributed in space, which then lets you answer nearest-house queries in sublinear time for each hub. The details are somewhat involved but you can find more information by searching about the "kNN" or "1NN" problem.