Let A is 2D -point set, |A| = n.Минимальное расстояние k-подмножество до оси x
Да OX = {point: point.y = 0} (по оси x).
Мне нужно найти R = min_{A_k from set of all k-subsets A} (max_{a from A_k} distance(a,OX)),
k = const, 1 <= k <= n.
Благодарим за помощь!
P.s. Я могу использовать R с точностью 1e-3 и a от A от целочисленной плоскости, a.x <=1000, a.y <= 1000.
Вы можете предварительно рассчитать distance(a,OX) за каждые a в A.
В настоящее время предположим, что A сортируется относительно distance(a,OX). Затем, учитывая (также отсортированное) подмножество A_k, max_{a from A_k} distance(a,OX), очевидно, является расстоянием последнего элемента. Теперь нам нужно найти подмножество A_k, где последний элемент минимален. Очевидно, что это подмножество, которое начинается с первого элемента и заканчивается на k-м элементе. Следовательно, R является k -ким наименьшим значением расстояния в A. Это можно найти с помощью QuickSelect в O(n).
OX, как вы описали, это ось y, а не x. Кроме того, ваше обозначение для R очень сложно найти в шрифте пишущей машинки. Вы можете написать это словами? – Gene