Results 1 to 4 of 4

Math Help - Point assignment problem

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    3

    Point assignment problem

    Hi everyone,

    I've got the following problem and I hope someone can help:

    I've got two sets of data points in Euclidean space. Both sets have the same number of data points. I now want to assign each point of set 1 to a point of set 2, so that the sum of the distances between the pairs of data points is minimal. Also, no two points of set 1 should be assigned to the same point of set 2 (i.e. there should be no point in any of the two sets that's not assigned to a point of the other set).

    I would assume that the problem can be solved using some sort of dynamic programming algorithm. When you set up a distance matrix between the two sets, this problem is equivalent to finding the minimum sum of N distance values with the constraint that none of the distance values was taken from the same row or column (N being the number of data points in each set).

    Has anyone any ideas how to solve this?

    Best,
    K.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Take a look at the Hungarian algorithm, which is designed to solve just such an assignment problem as you have there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    3
    Thanks Adrian, that's exactly what I was looking for.

    If anyone else has the same problem, I found a nice website (apart from the wikipedia page) that explains the problem with some visualizations and provides different solutions.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You're welcome! Have a good one. Thanks for the link.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inflection Point Problem; Revenue Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 9th 2011, 03:36 PM
  2. Point of Intersection problem
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 1st 2011, 01:26 PM
  3. Critical Point Problem...
    Posted in the Calculus Forum
    Replies: 4
    Last Post: March 20th 2010, 04:34 PM
  4. mid-point problem
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 4th 2009, 12:10 PM
  5. Partial Derrivatives Assignment problem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 25th 2007, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum