Найти точку в к-мерном пространстве

@DarthLenin · Регистрация: 22.09.2013

Студворк — интернет-сервис помощи студентам

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

@dikanev · 22.09.2013, 23:03

Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) требует $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2\cdot k$ сравнений. Чтобы его сократить:

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

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

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

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

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

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

Получаем сложность порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?N\log_{2}N\cdot k$ .

@DarthLenin · 23.09.2013, 00:37 **[ТС]**

Сообщение от dikanev

Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика)

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

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

@dikanev · 23.09.2013, 01:15

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

@Qwertiy · 23.09.2013, 11:41

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

@Igor3D · 23.09.2013, 12:17

Сообщение от Qwertiy

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

Как-то жирно, ресурсозатратно (в духе высокоуровневых языков). Я бы сортировал указатели на точки по x, y, z. Тогда образуется такая структурка

C++
1
2
3
struct CLine {
 int mBeg, mEnd;   // индекс в сортированном массиве, все точки от mBeg до mEnd имеют одинаковые x и y, разный z
};

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

@Qwertiy · 23.09.2013, 12:25

Сообщение от Igor3D

Я бы сортировал указатели на точки по x, y, z.

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

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

Сообщение от Qwertiy

Ассимптотика O(n^4).

Наврал.

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

@DarthLenin · 23.09.2013, 14:19 **[ТС]**

Имея set <все_точки>

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

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

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

@Qwertiy · 23.09.2013, 16:14

Сообщение от DarthLenin

Не могли бы вы поподробнее описать что мы делаем

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

@Igor3D · 23.09.2013, 17:17

Давайте закончим с "первоначальной" постановкой задачи

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

Сообщение от DarthLenin

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

Не слабо...

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

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

@DarthLenin · 23.09.2013, 17:26 **[ТС]**

Сообщение от Igor3D

Не слабо...

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

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

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

Сообщение от Igor3D

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

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

@Igor3D · 23.09.2013, 17:54

Сообщение от DarthLenin

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

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

@DarthLenin · 23.09.2013, 18:02 **[ТС]**

Сообщение от Igor3D

А что есть "изменение ровно d координат"? Это шаг величиной d по одной из осей?

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

@Igor3D · 23.09.2013, 18:14

Сообщение от DarthLenin

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

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

@DarthLenin · 23.09.2013, 18:22 **[ТС]**

Она может иметь больше 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.

@Igor3D · 23.09.2013, 19:46

(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 оси не влияет на расчет по другой

@DarthLenin · 23.09.2013, 20:25 **[ТС]**

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

@Igor3D · 24.09.2013, 09:52

Сообщение от DarthLenin

Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число).

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

@Qwertiy · 24.09.2013, 10:13

Сообщение от Igor3D

Напр (0, 0, 0) и (1, 1, 1) - соседи (если d = 1).

Нет...

@DarthLenin · 24.09.2013, 21:19 **[ТС]**

Сообщение от Igor3D

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

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

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24

	Найти точку в к-мерном пространстве 22.09.2013, 18:33. Показов 1460. Ответов 19 Метки нет (Все метки) Есть к-мерное дискретное (целочисленное) пространство. В нем отмечены некоторые точки. Нужно найти такую точку, что если через нее провести прямые параллельные базисным векторам, то на них будет лежать максимальное число точек. Если таких несколько, то нужно найти все. Как это можно сделать не перебирая все точки пространства? 0

@dikanev 21 / 21 / 1 Регистрация: 28.05.2010 Сообщений: 67
	22.09.2013, 23:03
	Пусть точек $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ . Решение в лоб (перебираем все пары точек, увеличиваем счетчик, если ровно одна из координат совпадает, в конце берем точки с максимальным значением счетчика) требует $https://www.cyberforum.ru/cgi-bin/latex.cgi?N^2\cdot k$ сравнений. Чтобы его сократить: 1. Сортируем точки по каждой из координат. Теперь точки у которых совпадает одна из координат лежат рядом в соответствующем массиве. 2. Перебираем точки 2.1. Каждую ищем в отсортированных массивах. 2.2. Составляем список точек, совпадающих по координате с данной. 2.3. Считаем точки, встречающиеся в этом списке ровно один раз. Увеличиваем на эту величину счетчик для текущей точки и на 1 для всех встречающихся один раз точек. 2.4. Удаляем текущую точку из отсортированных массивов. 3. Берем точки с максимальным значением счетчика. Получаем сложность порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?N\log_{2}N\cdot k$ . 0

@dikanev 21 / 21 / 1 Регистрация: 28.05.2010 Сообщений: 67
	23.09.2013, 01:15
	Вижу, что я неправильно понял условие задачи и предложил алгоритм для поиска наилучшей точки из отмеченных. Надо еще подумать, но уже поздно. Завтра подумаю. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	23.09.2013, 11:41
	Имея set <все_точки>, для каждой размерности сохранить map <координата, количество>. Последовательно для каждой пары осей перебираем точку из их map'ов. Полученная точка однозначно оределяет все вектора - считаем для них число точек, проверив дополнительно существует ли точка, которая является пересечением осей. Ассимптотика O(n^4). 0

@DarthLenin 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 18:22 [ТС]
	Она может иметь больше 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 1972 / 828 / 115 Регистрация: 01.10.2012 Сообщений: 4,991 Записей в блоге: 2
	23.09.2013, 19:46
	(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 0 / 0 / 0 Регистрация: 22.09.2013 Сообщений: 24
	23.09.2013, 20:25 [ТС]
	Что вы понимаете под шагом между соседями? Число координат в которых точки различны? Давайте определим, что сосед порядка d - это точка, которая может быть получена из текущей изменением d координат (неважно на какое число). При этом, при подсчете числа соседей учитываются только точки из данного на входе multiset, но точка относительно которой они считаются может быть произвольной. В этом случае, при d=1 у нас есть 2 точки дающие максимальное число соседей 1 порядка. Это точки 3,1,3 и 1,1,3. Они обе имеют по 3 соседа 1 порядка. Пустое множество вообще не может быть ответом никогда, если входное множество непусто. 0