2
$\begingroup$

My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question.

Looking for algorithm for closest available resource.

n people P1-Pn, n taxis T1-Tn, are in a 2 dimensional coordinate system eg x,y

Determine Person Taxi pairs if each person walks to the closest taxi that will be available to them, and not taken by another person. Ties of two (or more) people to same taxi can go to the person of lower index. Ties of two (or more) taxis as closest taxi can go to taxi of lowest index.

Does this go by a common problem name? What algorithms exist?

As for what algorithms exist, I can think of 2 right off but I doubt they be considered efficient. 1. use recursion, eg find closest person taxi pair, remove both from available list, and run again. 2. enumerate (n squared) all possible P-T pairs into binary tree sorted by distance value, and then traverse binary tree starting with lowest value until each P has unique T. 3. or can someone offer better algorithms?
Thank you

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "Ties of two (or more) people to same taxi can go to the person of lower index". Do you mean "must" since "can" implies no condition at all? $\endgroup$ – Apass.Jack Jan 15 at 8:14
  • $\begingroup$ Please add a reference to the original problem. Why is this important? Reasons 1) Credit should be attributed. 2) The original problem is probably stated clearer, especially when the current question is not clear. 3) A reference will motivate people easily. 4) A reference may save readers who look for related materials lots of time. $\endgroup$ – Apass.Jack Jan 15 at 14:09
  • $\begingroup$ Suppose $d(P_1, T_1)=2$, $d(P_1, T_2)=1$, $d(P_2, T_1)=2$, $d(P_2,T_2)=1$. Should $T_2$ be assigned to $P_1$ or $P_2$? Note that $T_2$ is the unique nearest taxi to $P_1$ and the unique nearest taxi to $P_2$. $\endgroup$ – Apass.Jack Jan 15 at 14:14
  • $\begingroup$ I mean, yes, taxi $T_2$ should be assigned to $P_1$ according to the tie-breaking rule. However, it is not explicitly defined in the question that we should then assign the nearest taxi (of the lowest index) other than $T_2$ to $P_2$ or we should declare there is no solution. My answer was done for the former interpretation. $\endgroup$ – Apass.Jack Jan 15 at 17:41
1
$\begingroup$

I would call this problem as closest matching between two equal sets with priority.

Here is an $O(n\log n)$ algorithm, assuming the distance is the 2-dimensional Euclidean distance. It might work with the Manhattan distance as well; however, I have not double checked that.

Build a balanced 2-d tree for all taxis in $O(n\log n)$ time. Attach to each node an inventory number, the number of all points in the rectangle or half plane represented by that node, which can be done in an $O(n)$-time tree traversal.

Now iterate over $P_1, P_2, \cdots, P_n$ in that order. For each person $P$, do the following.

Find all nearest taxis of $P$, using the inventory number and ignore the unavailable taxis, which takes (amortized) $O(\log n)$ time. Assign the taxi with the lowest index among them to $P$. Mark that taxi as unavailable. Subtract one from the inventory number attached to each node that contain $P$, which takes $O(\log n)$ time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The problem with k-d tree is that 2 nodes can be adjacent on the map (distance=1) and only meet at the root node. Or do you mean 1 tree per taxi ? $\endgroup$ – Vince Jan 15 at 12:57
  • $\begingroup$ May I ask whether you have read all text of how to find nearest point in Wikipedia? $\endgroup$ – Apass.Jack Jan 15 at 13:54
  • $\begingroup$ I suppose the coordinate system is not important, it can be there is a distance d between any person and a taxi. That said there would n² distances that need to calculated before you can determine any Taxi-Person pair to be the shortest distance. Maybe I explained it poorly, or but I don't understand how it could be less of (O(n²)). $\endgroup$ – Cris Jan 15 at 19:34
  • $\begingroup$ @Cris , the accepted answer to Closest pair of points between two sets in 2D can help understand why $O(n\log n)$ can be done. Voronoi diagram could have been used here had it not been for the lack of $O(\log n)$ algorithm to update the Voronoi diagram when a node is deleted. $\endgroup$ – Apass.Jack Jan 15 at 19:37
  • $\begingroup$ The 2-D Euclidean coordinate system may not be important indeed. I have to assume it because standard 2-d tree requires that assumption. Voronoi diagram requires it, too. $\endgroup$ – Apass.Jack Jan 15 at 19:43
0
$\begingroup$

I would compute all taxi-people pair distances (O(n²)).

Then I would solve the Stable marriage problem with Gale–Shapley algorithm (O(n²)). People looking for the closest taxi and taxis looking for the closest person.

An interesting point of your problem is that it is indeed symmetric on people and taxis. If it is solved considering taxis looking for people, the solution would be the same.

It makes an overall O(n²) solution quite easy to implement.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I assume you will run Gale-Shapley where the preference order based on the distance, where smaller distances have higher preference. Gale-Shapley will give a stable matching, but this does not guarantee that the closest P-T pairs are matched. So, this answer seems to solve a slightly different problem. $\endgroup$ – Discrete lizard♦ Jan 15 at 13:49
  • 1
    $\begingroup$ If you have computed all pairs, then just select the best taxi for first person, the best taxi remaining for second person, etc. Why do we need to use any other algorithm? $\endgroup$ – Apass.Jack Jan 15 at 13:50
  • $\begingroup$ @Discrete lizard. As you give symmetric weights (actually the distance) to each person and to each taxi, if you have a stable assignement it means: for each person, if there is a closer taxi than the one select, it is because this taxi had an even closer person. $\endgroup$ – Vince Jan 15 at 13:58
  • $\begingroup$ @Apass.Jack Then what is the solution of: 1..........A.2...........B ? $\endgroup$ – Vince Jan 15 at 13:59
  • 1
    $\begingroup$ No A1 & B2 is not stable because A prefers 2 and 2 prefers A. $\endgroup$ – Vince Jan 15 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.