Оптимизация двухпараметрической функции расстояния на отрезках (ACM ICPC Regionals Elim.)

Question

Эта проблема является подзадачей задачи, поставленной в ACM ICPC Kanpur Regionals Раунда. Раунд:

Для двух отрезков, ограниченных 2D точками (Pa, Pb) и (Pc, Pd) соответственно, найдите pq (в диапазоне [0,1]), который минимизирует функцию

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

(фактически Px и Py - это точки на отрезках, а функция кодирует стоимость перехода от Pa к Pd черезсвязующее звено, стоимость которого в k раз превышает евклидово расстояние)

Некоторые замечания относительно этой функции:

1. Параллельные отрезки всегда будут вызывать хотя бы один из p и qбыть либо 0, либо 1
2. Пересекающиеся отрезки всегда будут вызывать p и q для определения точки пересечения отрезков (для подтверждения этого можно применить неравенство треугольника)

Вопрос: в общем случае, когда линии наклонены и потенциально разделены, как мы минимизируем эту функцию?

Answer 1

Я думаю, вы должны быть в состоянии взять частные производные f относительно p и q, установить их в 0 и решить для p и q. Это даст вам (местный) минимум. Если минимум имеет 0 <= p <= 1 и 0 <= q <= 1, все готово, в противном случае проверьте четыре конечные точки (p=0,q=1 и т. Д.).

Я не уверен, что это справится со всеми дегенеративными состояниями, но это должно быть хорошим началом.