Constructing pairwise disjoint paths with few links

Let P be a simple polygon and let {(u₁, u′₁), (u₂, u′₂),(u_m, u′_m)} be a set of m pairs of distinct vertices of P, where for every distinct i, j m, there exist pairwise disjoint (nonintersecting) paths connecting u_i to u′_i and u_j to u′_j. We wish to construct m pairwise disjoint paths in the interior of P connecting u _i to u′_i for i = 1, ,m, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using O(M) line segments in O(n log m + M log m) time, where M is the number of line segments in the optimal solution and n is the size of the polygon.