Найти центральную точку в наборе точек метрического пространства меньше, чем

У меня есть набор из точек, которые определены в метрическом пространстве - так что я могу измерить «расстояние» между точками, но больше ничего. Я хочу найти самую центральную точку в этом наборе, которую я определяю как точку с минимальной суммой расстояний до всех остальных точек. Метрические вычисления являются медленными, поэтому их следует избегать, где это возможно. $n$

Очевидный способ найти эту точку использует метрических вычислений расстояния, так как он просто (a) вычисляет для каждой точки сумму расстояний до всех других точек, а затем (b) принимает минимальную точку. $n^2$

Есть ли способ сделать это при сравнении расстояний меньше чем ? (Вероятно, используя неравенство треугольника в некотором роде, что должно соответствовать моей метрике.) $O(n^2)$

Хорошего приближения может быть достаточно, если точного метода не существует.

complexity-theory computational-geometry lower-bounds search-problem Open Door Logistics
источник

Без неравенства треугольника (или какого-либо другого способа получения информации о неизмеренных ребрах) является единственным решением; это видно по аргументу антагониста.

O (n^{2})

$O(n^2)$

Китцил

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

Open Door Logistics

По сути, это вычисление радиограмм графа с равенством треугольников.

Каве

@Kaveh Полагаю, ты имеешь в виду радиус ... если график не имеет ломаной кромки. Я удостоверяюсь, поскольку есть слишком большой словарный запас, который я не знаю. --- Но тогда это полный граф, а входным размером является только количество вершин.

Бабу

@OpenDoorLogistics Если в нем нет неравенства треугольника, то по определению это не метрическое пространство. Пожалуйста, уточните вопрос: если вы знаете, что это метрическое пространство, то вы знаете, что оно имеет неравенство треугольника; если вы не знаете, что оно имеет неравенство треугольника, вы не можете утверждать, что это метрическое пространство.

Дэвид Ричерби

Ответы:

$\Theta(n^2)$

$1$ $0.9$ $1.0$ $1.1$

$\mathbb{R}^d$ $O((d+1)n)$ $d+1$

$d+1$ $P$ $P$ $P$ $P$ $P$ $O(n^2)$

DW
источник

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

n

$n$

@DW Спасибо - мы могли бы сделать что-нибудь лучше в среднем случае, хотя? Это вызвано реальной проблемой, поэтому данные, скорее всего, будут «средними» (что бы это ни значило).

Логистика открытых дверей

@all - извиняюсь за путаницу re: metric (я специалист по теоретическим знаниям). Моя функция расстояния определенно подчиняется 4 критериев для метрического пространства, согласно определению Википедии метрического пространства ссылки .

Логистика открытых дверей

@ OpenDorLogistics, я добавил один особый случай, когда кажется возможным сделать лучше.

Проверьте работу Петра Индика по быстрым алгоритмам для метрических пространств. ( Сублинейные алгоритмы для задач метрического пространства , в трудах STOC '99 , с.428–434. ACM, 1999; PS ) В разделе 3 приведен приближенный 1-медианный алгоритм в линейном времени.

user71641
источник

Не могли бы вы дать краткое изложение алгоритма? В идеале мы ищем полные ответы, а не ссылки на внешний контент.

Дэвид Ричерби

Извиняюсь за очень медленный ответ. Я, очевидно, не очень часто проверяю StackExchange. Я думаю, что мне потребовалось бы больше часа, чтобы написать наполовину приличное резюме, в то время как статья Петра прекрасно написана, очень четко объясняет алгоритм и имеет все точные определения рядом с ним. Поэтому я лично настоятельно рекомендую использовать этот высококачественный внешний контент, а не внутренний контент среднего качества, который я мог бы производить. Короткий ответ: если вы хотите просто найти приблизительную медиану, вы можете сделать это за линейное время O (n).

user71641