@DarthLenin

Есть к-мерное дискретное (целочисленное) пространство. В нем отмечены некоторые точки. Нужно найти такую точку, что если через нее провести прямые параллельные базисным векторам, то на них будет лежать максимальное число точек. Если таких несколько, то нужно найти все. Как это можно сделать не перебирая все точки пространства?

0

@dikanev

Пусть точек . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) требует сравнений. Чтобы его сократить:

1. Сортируем точки по каждой из координат. Теперь точки у которых совпадает одна из координат лежат рядом в соответствующем массиве.

2. Перебираем точки
2.1. Каждую ищем в отсортированных массивах.

2.2. Составляем список точек, совпадающих по координате с данной.

2.3. Считаем точки, встречающиеся в этом списке ровно один раз. Увеличиваем на эту величину счетчик для текущей точки и на 1 для всех встречающихся один раз точек.

2.4. Удаляем текущую точку из отсортированных массивов.

3. Берем точки с максимальным значением счетчика.

Получаем сложность порядка .

0

@DarthLenin

Может получиться так, что нужной точки нет в исходном массиве. Пример датасета для 2-мерного пространства:
3,3 1,3 3,3 0,2 2,2 1,3
Ответом здесь будут точки 0,3 и 2,3

Добавлено через 8 минут
Замечу, что для 2мерного случая решение несложное, но с обощением на к-мерность возникают проблемы. Например, для 3мерного случая нам придется рассматривать каждую плоскость соответствующую 3ей координате. Собственно вопрос в том, как избежать такого перебора.
Кроме того, если ровно одна координата совпадает, то через такие точки нельзя провести прямую параллельную базису. Если ровно одна координата различается, тогда можно.

0

@dikanev

Вижу, что я неправильно понял условие задачи и предложил алгоритм для поиска наилучшей точки из отмеченных. Надо еще подумать, но уже поздно. Завтра подумаю.

0

@Qwertiy

Имея set <все_точки>, для каждой размерности сохранить map <координата, количество>. Последовательно для каждой пары осей перебираем точку из их map'ов. Полученная точка однозначно оределяет все вектора - считаем для них число точек, проверив дополнительно существует ли точка, которая является пересечением осей. Ассимптотика O(n^4).

0

@Igor3D

Как-то жирно, ресурсозатратно (в духе высокоуровневых языков). Я бы сортировал указатели на точки по x, y, z. Тогда образуется такая структурка
Сделал так же для всех комбинаций осей (y, z, x)(z, x, y) - имею 3 контейнера CLine. Отсортировал 2 последних по X. Иду по первому, двоичным поиском ищу в 2 последних. Повторяю эту процедуру число осей - 1 раз

0

@Qwertiy

А ничего что пространство k-мерное, а не 3-мерное?

Добавлено через 3 минуты
Наврал.

Добавлено через 3 минуты
Ассимптотика O(k^3*n^2):
k^2 - перебор двух осей
n^2 - перебор точек на осях
k - подсчёт по оставшимся k-2 осям

0

@DarthLenin

Извиняюсь, я забыл упомянуть, что у нас может быть "несколько точек в одной точке". Так что на входе у нас multiset.

И я не слишком понял идею алгоритма. Не могли бы вы поподробнее описать что мы делаем на примере такого датасета:
1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3

Добавлено через 24 минуты
По сути задачу можно сформулировать так: найти такую точку, чтобы как можно большее число точек, подающихся на вход, отличалось от нее не более чем в 1 координате (на самом деле не более чем в d, но мне хотя бы при d=1 разобраться)

0

@Qwertiy

Хм.. Кажется, я бред написал...
Думал, что так получится, но тут что-то не то

0

@Igor3D

Давайте закончим с "первоначальной" постановкой задачи Здесь все ясно: для каждой точки заводим k счетчиков (к - число осей). Сортируя точки k раз заполняем счетчики используя интервал точек сортированного массива отличающихся лишь по одной оси (последний ключ сортировки)

Не слабо... Др словами - "найти точку с максимальной плотностью (d)"?

Добавлено через 3 минуты
Неясно что имеется ввиду. Напр 2 точки, расстояние между ними по x < 1. но по др оси напр 1000. Такие точки считаются или как?

0

@DarthLenin

Ну...Не вполне уверен, что я правильно понимаю что такое плотность(d). Точки могут не быть сосредоточены геометрически близко. Но для 3мерного пространства это будет означать при d=1 что мы проводим через точку прямые, при d=2 - плоскости, при d=3 - куб (ну тут уже, очевидно, подойдет любая точка пространства). В общем, по-моему переформулировка получилась более понятной, т.к. она избавляет от геометрического смысла.

Добавлено через 4 минуты
Пространство, как я писал, дискретное. Допускаются только целые координаты. Если точки отличаются только по одной координате, неважно на сколько, то они лежат на одной прямой (параллельной какому-то базисному вектору) и следовательно считаются. Еще раз сформулирую: нужно найти такую точку, чтобы изменением ровно d координат (раз уж упомянул, будем говорить более обощенно, чтобы не путаться), можно было получить как можно больше точек из входного набора

0

@Igor3D

А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей? Напр d = 1, точки (5, 5, 1)(5, 5, 2)(5, 5, 3) считаются, каждая точка имеет минимум 2 годных соседей. Тогда кстраивает предыдущее решение. Все это мне напоминпет воксели

0

@DarthLenin

Нет, это шаг произвольной длины по d осям
Например, из (5, 5, 1) можно получить (5, 5, 3) изменив одну координату (третью). Тут d=1. Например, между (5,5,1) и (5,3,2) d=2

0

@Igor3D

То есть средняя точка имеет минимум 2 соседей, крайние - минимум 1. Все равно устраивает предыдущее решение

0

@DarthLenin

Она может иметь больше 2 соседей, может вообще не иметь соседей, главное, чтобы все точки различались ровно в одних и тех же координатах.
Например, точки 0,0,1 0,0,2 0,0,3 0,0,4 все являются соседними друг другу т.к. любую из них можно получить изменением 1 координаты в любой другой. Возможно я просто не понимаю то, что вы хотите сказать. Если вы считаете, что ваш алгоритм работает, то не могли бы вы показать конкретные шаги на датасете который я писал выше. Напишу еще раз - 1,3,3 2,1,3 3,3,3 1,0,2 1,2,2 0,1,3.

0

@Igor3D

(1,3,3) (2,1,3) (3,3,3) (1,0,2) (1,2,2) (0,1,3)

Сортируем по x, y, z
(0,1,3) (1,0,2) (1,2,2) (1,3,3) (2,1,3) (3,3,3) - никакие 2 точки не лежат на оси Z

Сортируем по y, z, x
(1,0,2) (0,1,3) (2,1,3) (1,2,2) (1,3,3) (3,3,3) - 2 группы лежат на оси X (x, 1, 3) + (x, 3, 3)

Сортируем по z, x, y
(1,0,2) (1,2,2) (0,1,3) (2,1,3) (1,3,3) (3,3,3) - 1 группа лежит на оси Y (1, y, 2)

Дальше отсеиваете группы по правилам как хотите. Напр если шаг между соседями 1, то ответ "пусто". Просчитав группу запоминаете результат в счетчикаx точки. Расчет по 1 оси не влияет на расчет по другой

0

@DarthLenin

Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число). При этом, при подсчете числа соседей учитываются только точки из данного на входе multiset, но точка относительно которой они считаются может быть произвольной. В этом случае, при d=1 у нас есть 2 точки дающие максимальное число соседей 1 порядка. Это точки 3,1,3 и 1,1,3. Они обе имеют по 3 соседа 1 порядка. Пустое множество вообще не может быть ответом никогда, если входное множество непусто.

0

@Igor3D

Я понял координатЫ (именно одной). А оказывается любого числа координат (от 1 до k) но строго на одно число. Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1). Также искомая точка может и не входить в исходное множество. Теперь все правильно?

0

@Qwertiy

Нет...

0

@DarthLenin

Нет, они различаются в трех координатах. Они были бы соседями только при d >= 3
Например, (0, 0, 0) и (0, 0, 500) - соседи при d=1

0