Поиск подмножества на плоскости с минимальным диаметром

[trozki_187]

Добрый день.

Дан массив $A$ из $N$ целочисленных положительных пар точек (можно думать в ключе прямоугольников с высотой $h$ и шириной $v$). Нужно найти $K$ точек с минимальным диаметром.
Диаметром множества называется максимальное расстояние между двумя точками множества. В задаче используется расстояние Чебышева, т.е. $d(a, b) = \max( |a_x - b_x|, |a_y - b_y|)$.

Ограничения: $2 \leq K \leq N \leq 10^5$, $1 \leq x \leq y \leq 400$

Мои наблюдения и мысли:
В силу специфики расстояния, диаметр на $N$ точках можно считать за линейное время от $N$ как $\max(\max(A_x) - \min(A_x), \max(A_y) - \min(A_y))$, где $A_x$ и $A_y$ - это массивы из $x$-координат и $y$-координат, соответственно.

Можно попробовать бинарный поиск диаметра с диапазоном от 0 до диаметра всех $N$ точек, но нужно уметь быстро посчитать, существует ли хотя бы $K$ точек с диаметром $m$ среди всех точек, где $m$ - текущее среднее значение в бинарном поиске. Жадные алгоритмы, которые у меня возникают для такого подсчета кажутся мне некорректными, но, возможно, я что-то упускаю.

Спасибо всем за помощь!

[mihaild]

У вас же всего лишь 160000 различных координат получается. Сможете быстро посчитать, сколько точек в квадрате с заданными углами? Если да, то просто перебираете один угол квадрата, и бинпоиском по стороне находите нужную для этого угла сторону.

[trozki_187]

mihaild в сообщении #1605847 писал(а):

У вас же всего лишь 160000 различных координат получается. Сможете быстро посчитать, сколько точек в квадрате с заданными углами? Если да, то просто перебираете один угол квадрата, и бинпоиском по стороне находите нужную для этого угла сторону.

Я правильно понимаю, что Вы предлагаете цикл по всем возможным координатам(400х400) (пусть это будет правый верхний угол обрамляющего квадрата), внутри которого бин-поиском определяется длина его стороны, такая что, хотя бы $K$ точек в этот квадрат входят. Процедура возвращает минимальную найденную длину в этом цикле. Так?

Вместо 400, наверное можно использовать $l = \max(\max(A_x), \max(A_y))$. Подсчет количества точек внутри квадрата с заданным углом и стороной займет $O(N)$. С учетом бин-поиска по стороне $O(\log(l) \times N)$. С учетом внешнего цикла, асимптотика процедуры $O(l^2 \times \log(l) \times N)$. Так? Обязателен ли цикл
по всей сетке?

Спасибо за Ваш комментарий!

[mihaild]

trozki_187 в сообщении #1605850 писал(а):

Подсчет количества точек внутри квадрата с заданным углом и стороной займет $O(N)$.

Если сделать некоторую предобработку за $O(l^2)$, то после можно будет считать число точек в произвольном прямоугольнике за $O(1)$.

[trozki_187]

mihaild в сообщении #1605857 писал(а):

Если сделать некоторую предобработку за $O(l^2)$, то после можно будет считать число точек в произвольном прямоугольнике за $O(1)$.

Не подскажете? не соображу, что за предобработка.

[Null]

trozki_187 в сообщении #1605860 писал(а):

Не подскажете? не соображу, что за предобработка.

Для каждого $(s,t)$ количество точек с координатами $\{(x,y)|x\le s,y\le t\}$

[trozki_187]

Null в сообщении #1605861 писал(а):

Для каждого $(s,t)$ количество точек с координатами $\{(x,y)|x\le s,y\le t\}$

Да, но сторона квадрата варьируется. Поэтому, это вроде как, не поможет. Таким образом можно посчитать количество точек в прямоугольнике, у которого один угол зафиксирован в (0, 0).

[Null]

trozki_187 в сообщении #1605864 писал(а):

Таким образом можно посчитать количество точек в прямоугольнике, у которого один угол зафиксирован в (0, 0).

Попробуйте поскладывать-повычетать эти прямоугольники(как множества)

[trozki_187]

Null в сообщении #1605865 писал(а):

Попробуйте поскладывать-повычетать эти прямоугольники(как множества)

Я Вас понял, спасибо, но такая предобработка предполагает сканирование массива $A$, не так ли? То есть $O(N \times l^2)$

[Null]

В начале данные надо сжать: заводим массив $l\times l$ и считаем в нем количество точек с координатами $(i,j)$. В общем сложность $O(l^2 \log(l)+N)$, не влазьте за нее.

[mihaild]

Такая предобработка делается за $O(l^2 + N)$. Заведите массив размера $l^2$, заполните его из исходного и забудьте про исходный.

Кстати после этого можно ещё и без бинпоиска обойтись, если правильно квадраты перебирать.

[trozki_187]

mihaild в сообщении #1605871 писал(а):

Кстати после этого можно ещё и без бинпоиска обойтись, если правильно квадраты перебирать.

Еще раз спасибо! За $O(l^2 \times \log(l) +N)$ реализовал. Не подскажете как обойтись без $\log(l)$?

[mihaild]

Как найти минимальный размер квадрата, содержащего $K$ точек, верхний правый (и соответственно нижний левый) угол которого имеет координаты $x = y$, за $O(l)$ (без перебора всех таких квадратов, что было бы $O(l^2)$)?

[trozki_187]

mihaild в сообщении #1605885 писал(а):

верхний правый (и соответственно нижний левый) угол которого имеет координаты $x = y$, за $O(l)$ (без перебора всех таких квадратов, что было бы $O(l^2)$)?

Правильно понимаю, что речь идет о квадратах с двумя углами на диагонали? Их же всего порядка $l$.

[mihaild]

trozki_187 в сообщении #1605887 писал(а):

Правильно понимаю, что речь идет о квадратах с двумя углами на диагонали? Их же всего порядка $l$

Да, правильно.
Нет, их $O(l^2)$. Диагональ имеет длину $O(l)$, а квадрат задается двумя точками из неё.