\Section{2 указателя}{30 октября}{Андрей Гусев}

Задача: есть $n$ точек. Необходимо выбрать $k$ точек так, чтобы сумма расстояний от каждой из исходных $n$ точек до ближайшей выбранной была минимально возможной. Ранее мы решили задачу, используя следующую теорему: существуют оптимальные наборы точек, для которых выполняется условие: $p[k - 1, n] \le p[k, n] \le p[k, n + 1]$, где $p[k, n]$ - это координата середины отрезка между последней и предпоследней точками.

\Subsection {Доказательство}

Для начала поймём, что каждая выбрання точка будет ближайшей для тех точек, которые находятся между серединами отрезков от неё до соседей назовём такой отрезок областью влияния выбранной точки.

Сведём первое неравенство ко второму. Предположим, что оно ложно, то есть в оптимальных наборах $k$ и $k - 1$ точек для некоторого исходного набора $p[k - 1, n] > p[k, n]$. Возмём один набор точек и выберем для него сначала $k$, потом $k - 1$ точку. Развернём оба набора точек. Посмотрим на границы отрезков влияния выбранных точек. Первая граница правее у второй выборки точек. Ясно, что при последовательном переходе к следующим границам настанет момент, когда либо границы отрезков в разных выборках сравняются, либо граница в первой окажется правее соответствующей границы во второй. В случае, наличия совпадающих границ отрезки левее них представляют собой различные решения одной и той же задачи, поютому можно заменить часть точек в одной из выборок так, что она останется оптимальной, а разбиение на отрезки до совпадающих границ совпадёт со второй выборкой, то есть первое неравенство выполнится. Если же граница для первой выборки обгоняет вторую, отбросим точки правее соответствующей границы во второй выборке и получим противоречие с первым неравенством.

Теперь докажем второе неравенство ($p[k, n] \le p[k, n + 1]$). Пусть $q$ - координата последней выбранной точки. 

Рассмотрим случай $q_2 \ge q_1$. Возьмём четыре набора точек. Первый - оптимальный выбор $k$ точек для $n$ исходных. Второй - $n + 1$ исходная точка, $p = p_1$. Третий - оптимальный выбор $k$ точек для $n + 1$ исходной $p = p_2$, $q = q_2$. Четвёртый - снова $n$ точек дано, 
$q = q_1$, $p = p_2$.

Обозначим $f_i$ сумму расстояний от каждой точки до ближайшей выбранной в $i$-м наборе; $F_1$ - сумму расстояний для точек левее $p_1$ (то есть для точек до $p$ в первых двух наборах), $F_2$ - сумму расстояний для точек левее $p_2$, (то есть для точек до $p$ в двух последних наборах).

$f_1 - f_4 = (F_1 - F_2) + (\sum\limits_{i = p1}^{n}dist(p_i, q_1) - \sum\limits_{i = p1}^{n}dist(p_i, q_1)) - \sum\limits_{i = p_2}^{p_1 - 1}dist(i, q_1)$

$f_2 - f_3 = (F_1 - F_2) + (\sum\limits_{i = p1}^{n + 1}dist(p_i, q_1) - \sum\limits_{i = p1}^{n + 1}dist(p_i, q_1)) - \sum\limits_{i = p_2}^{p_1 - 1}dist(i, q_2)$

$((p_1..n - q_1) - (p_1..n - q_1)) = 0 = ((p_1..n + 1 - q_1) - (p_1..n + 1 - q_1))$ - расстояния от $q_i$ до точек правее $p_1$.

$\sum\limits_{i = p_2}^{p_1 - 1}dist(i, q_2) < \sum\limits_{i = p_1}^{p_1 - 1}dist(i, q_1)$, т.к. $q_2 \ge q_1$ - расстояния от $q_i$ до точек правее.

Отсюда $(f_1 - f_4) \ge (f_2 - f_3)$. Из оптимальности третьего набора $f_2 - f_3 \ge 0$. По транзитивности $f_1 - f_4 \ge 0 \Rightarrow f_1 \ge f_4$, следовательно, четвёртый набор оптимален. Мы нашли такой набор длины $n$, для которого $p[n, k] \le p[n + 1, k]$. Неравенство доказано.

Теперь рассмотрим случай $q_2 < q_1$. Снова возьмём черыре набора точек. Первый - оптисмальное решшение задачи для $n$ точек. Второй - $n + 1$ точка дана, $p = p_1$. Третий - решение задачи для $n + 1$ точки. Четвёртый - $n$ точек дано, выббранные - как в третьем. $p_2$ - $p$ для двух последних наборов.

Изменения при переходе от первого набока ко второму - добавление одной точки, поэтому увеличивается на $x - q_1$, где x - координата добавленной точки. При переходе от второго набора к третьему сумма расстояний может только уменьшится, т.к. третий оптимален. При переходе от третьего набора к четвертому сумма расстояний опять уменьшается за счёт исчезновения последне точки, причём, поскольку $q_2 < q_1 < x$, модуль этого изменения больше, чем при первом переходе. Отсюда видно, что сумма расстояний в последнем наборе меньше, чем в первом, значит, мы нашли оптмальный ответ с $p \le p_2$. Неравенство доказано.
{document}