5

I'm trying to find the distance of a point (in 4 dimensions, only 2 are shown here) (any coloured crosses in the figure) to a supposed Pareto frontier (black line). This line represents the best Pareto frontier representation during an optimization process.

Pareto = [[0.3875575798354123, -2.4122340425531914], [0.37707675586149786, -2.398936170212766], [0.38176077842761763, -2.4069148936170213], [0.4080534133844003, -2.4914285714285715], [0.35963459448268725, -2.3631532329495126], [0.34395217638838566, -2.3579931972789114], [0.32203302106516224, -2.344858156028369], [0.36742404637441123, -2.3886054421768708], [0.40461156254852226, -2.4141156462585034], [0.36387868122767975, -2.375], [0.3393199109776927, -2.348404255319149]]

Right now, I calculate the distance from any point to the Pareto frontier like this:

def dominates(row, rowCandidate):
return all(r >= rc for r, rc in zip(row, rowCandidate))

def dist2Pareto(pareto,candidate):
    listDist = []

    dominateN = 0
    dominatePoss = 0
    if len(pareto) >= 2:
        for i in pareto:
            if i != candidate:
                dominatePoss += 1
                dominate = dominates(candidate,i)
                if dominate == True:
                    dominateN += 1
                listDist.append(np.linalg.norm(np.array(i)-np.array(candidate)))

        listDist.sort()

        if dominateN == len(pareto):
            print "beyond"            
            return listDist[0]  
        else:
            return listDist[0]

Where I calculate the distance to each point of the black line, and retrieve the shortest distance (distance to the closest point of the known Frontier).

However, I feel I should calculate the distance to the closest line segment instead. How would I go about achieving this?

enter image description here

ali_m
  • 71,714
  • 23
  • 223
  • 298
Lucien S.
  • 5,123
  • 10
  • 52
  • 88
  • 1
    This is an algorithm question, and would probably be better migrated to one of the other SE sites... but which? Math.SE has a lot of hits for "point spline distance". – smci Nov 11 '15 at 21:19
  • 1
    Well, when you are able to find the two closest points on the pareto frontier, the linear connection between these two points is probably the closest line element, isn't it? Thus, as a second step you can calculate the distance between the line and the point. – jkalden Nov 12 '15 at 13:31
  • Do we take it this a piecewise-linear approximation, not an actual spline? – smci Nov 12 '15 at 22:15
  • 1
    @jkalden. Your assumption is not correct. Imagine a very long line segment that is close to the point. It could have endpoints that are further from the point of interest than a shorter segment which is really further away. – Mad Physicist Dec 08 '15 at 02:07

1 Answers1

1

The formula for the coordinates of the nearest point on the line is given here. Specifically, you are interested in the one called "line defined by two points". For posterity, the formula is:

Formula for distance between a line defined by two points, and a third point

Because the frontier is relatively simple, you can loop through each two-point line segment in the frontier, and calculate the closest distance for each, keeping the smallest. You could introduce other constraints / pre-computations to limit the number of calculations required.

Benjamin
  • 11,560
  • 13
  • 70
  • 119
  • Your formula is a bit difficult to extrapolate to higher dimensions, but the derivation can be used to re-express it in terms of dot products, which would make it 100% applicable to the original question. – Mad Physicist Dec 08 '15 at 02:10
  • @ Mad Physicist: Yes, I missed that in the original question. There is a good formulation here: http://programmers.stackexchange.com/a/168577 – Benjamin Dec 08 '15 at 02:15
  • Also, this is the distance to the whole line, not the line segment. See this SO post for some sample calculations in different languages: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment – Mad Physicist Dec 08 '15 at 02:15
  • I'm still voting you up because you fully addressed the concept and I consider it laziness on the OP's part not to have Googled the answer before posting. – Mad Physicist Dec 08 '15 at 02:17