Блог

Из нескольких источников я узнал, что в алгоритме ближайшей пары «разделяй и властвуй» при нахождении особых случаев (пар точек в разных половинах) вы просматриваете не более 7 индексов перед любой заданной точкой. Когда я разобрался с этим, кажется, что вам сойдет с рук только 6 или, может быть, даже 5.

Если вы выполняете классическое доказательство, в котором вы рисуете квадраты с длиной стороны d (минимальное значение из рекурсивных вызовов), вы можете разместить только 7 точек (или, может быть, 6?) между 2 точками, Что означает, что вам нужно всего лишь просмотреть 6 (или 5?) точек вперед, чтобы найти минимальное значение. Это потому, что единственный способ, которым вы можете «подогнать 8 точек», — это поместить точки в углы, но это невозможно, потому что квадраты имеют общие углы, а также потому, что если вы сделаете свои границы строгими (и не меньше или равными), это также невозможно.

Извините за то, что так неясно, для описания всего этого требуется целая лекция, поэтому я, очевидно, не могу сделать это здесь. Чтобы быть более понятным, может кто-нибудь привести мне пример из 8 точек, которые удовлетворяют условиям, а также такие, что самая высокая и самая низкая точки находятся в разных половинах и являются самыми близкими? Условия заключаются в том, что пары точек в одной половине находятся на расстоянии не менее d друг от друга.