This problem is a subproblem of a problem posed in the ACM ICPC Kanpur Regionals Elimination Round:
Given 2 line segments bounded by the 2D points (Pa, Pb)
and (Pc, Pd)
respectively, find p
and q
(in the range [0,1]
) that minimizes the function
f(p, q) = D(Px, Pa) + D(Py, Pd) + k D(Px, Py) where
2 <= k <= 5,
Px = p Pa + (1-p) Pb,
Py = q Pc + (1-q) Pd and
D(x, y) is the euclidean distance between points x and y
(effectively, Px and Py are points on the line segments and the function encodes the cost of going from Pa to Pd through a connecting link of a cost that is k times the euclidean distance)
Some observations regarding this function:
- Parallel line segments will always cause atleast one of
p
andq
to be either 0 or 1 Intersecting line segments will always causep
andq
to locate the point of intersection of the line segments (the triangle inequality can be applied to prove this)
The question: In the general case where the lines are inclined and potentially separated, how do we minimize this function?