Unless there is another optimization, it very well may not be. I have no idea how many passes it would even take to get from an average pairing to a non-intersecting pairing, but each one might require an O(n Log n) task of actually finding an intersection.

Depending on how long it takes, there might be a shortcut by starting with a pairing that has a low total line segment length (as each pass reduces length, there would be fewer possible reductions necessary)

Hmm, finding the lowest total line segment length would be sufficient too, with no passes of intersection checking at all - if there was an intersection, removing it could reduce the total length.