Encontre o ponto central em um conjunto de pontos no espaço métrico, em menos de

Eu tenho um conjunto de pontos que são definidos em um espaço métrico - para que eu possa medir uma 'distância' entre pontos, mas nada mais. Quero encontrar o ponto mais central desse conjunto, que defino como o ponto com a soma mínima de distâncias para todos os outros pontos. O cálculo da métrica é lento e, portanto, deve ser evitado sempre que possível. $n$

A maneira óbvia de encontrar esse ponto usa cálculos de distância métrica, pois simplesmente (a) calcula para cada ponto a soma das distâncias para todos os outros pontos e, em seguida, (b) assume o ponto mínimo. $n^2$

Existe uma maneira de fazer isso em comparações de distância menor que ? (Provavelmente fazendo uso da desigualdade do triângulo de alguma forma, o que deve se aplicar à minha métrica.) $O(n^2)$

Uma boa aproximação pode ser suficiente se um método exato não existir.

complexity-theory computational-geometry lower-bounds search-problem Logística de portas abertas
fonte

Sem a desigualdade do triângulo (ou alguma outra maneira de obter informações sobre arestas não medidas),

é a única solução; isso pode ser visto por um argumento antagonista.

O (n^{2})

$O(n^2)$

Kittsil

Suponha que a desigualdade do triângulo esteja disponível - deve ser para a minha métrica.

Open Door Logistics

Isto é essencialmente computando os rádios de um gráfico com igualdade de triângulo.

Kaveh

@ Kaveh Eu acho que você quer dizer o raio ... a menos que o gráfico tenha uma borda quebrada. Estou me certificando de que há muito vocabulário que não conheço. --- Mas é um gráfico completo, e o tamanho da entrada é apenas o número de vértices.

babou

@OpenDoorLogistics Se não tiver a desigualdade do triângulo, não é um espaço métrico, por definição. Por favor, esclareça a pergunta: se você sabe que é um espaço métrico, então sabe que tem a desigualdade do triângulo; se você não sabe que tem a desigualdade do triângulo, não pode afirmar que é um espaço métrico.

precisa saber é o seguinte

Respostas:

Não. Você não pode fazer melhor que no pior caso. $\Theta(n^2)$

Considere um arranjo de pontos em que cada par de pontos esteja à distância um do outro. (Essa é uma configuração possível.) Então você não pode fazer melhor do que examinar todas as arestas. Em particular, se houver alguma aresta que você não examinou, um adversário poderá escolher o comprimento dessa aresta para , ou ; todas essas escolhas são consistentes com todas as outras observações que você fez e com os requisitos de uma métrica (por exemplo, com a desigualdade do triângulo), portanto, todas as três são possíveis; mas eles exigem saídas diferentes. Portanto, se o seu algoritmo não examinar essa aresta e emitir alguma coisa, um adversário sempre poderá escolher um comprimento para a aresta não examinada que fará com que a saída do seu algoritmo esteja errada. $1$ $0.9$ $1.0$ $1.1$

No entanto, se você souber que todos os pontos vivem em (mesmo que você não tenha suas coordenadas), o problema pode ser resolvido medindo-se as distâncias , assumindo que não há degenerescências (nenhum subconjunto de pontos são co-planares). $\mathbb{R}^d$ $O((d+1)n)$ $d+1$

Em particular, escolha pontos aleatoriamente. Estes serão pontos de ancoragem. Dadas as distâncias aos pares, é possível calcular coordenadas para elas que sejam consistentes com as distâncias aos pares. Agora, para todos os outros pontos , calcule a distância de a cada um dos pontos de ancoragem. Usando triangulação e estas distâncias, você pode calcular a localização de em relação aos pontos de ancoragem e, portanto, as coordenadas para . Faça isso para cada ponto não-âncora $d+1$ $P$ $P$ $P$ $P$ $P$ . Agora você tem coordenadas para cada ponto e pode usá-las para encontrar o ponto central sem pedir ao oráculo que lhe forneça mais distâncias aos pares. Eu não sei se este último passo pode ser feito mais rápido do que tempo , mas isso pode ser feito sem medir nenhum mais distâncias de pares. $O(n^2)$

DW
fonte

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

n

$n$

@ DW Obrigado - poderíamos fazer algo melhor no caso médio embora? Isso é motivado por um problema do mundo real; portanto, é provável que os dados sejam "médios" (o que isso possa significar).

Open Door Logistics

@all - desculpas pela confusão re: métrica (sou leigo em CS teórico). Minha função de distância definitivamente obedece aos 4 critérios para um espaço métrico, conforme a definição da Wikipedia de um link de espaço métrico .

Open Door Logistics

@OpenDoorLogistics, adicionei um caso especial em que parece possível fazer melhor.

Confira o trabalho de Piotr Indyk sobre algoritmos rápidos para espaços métricos. ( Algoritmos subliminares para problemas de espaço métrico , em Proceedings of STOC '99 , pp.428-434. ACM, 1999; PS ) A seção 3 fornece um algoritmo de 1 mediana aproximada em tempo linear.

user71641
fonte

Você poderia dar um resumo do algoritmo? O ideal é procurar respostas completas, em vez de links para conteúdo externo.

David Richerby

Desculpas pela resposta muito lenta. Obviamente, não checo o StackExchange com muita frequência. Eu acho que levaria mais de uma hora para escrever um resumo meio decente, enquanto o artigo de Piotr é lindamente escrito, explica o algoritmo com muita clareza e tem todas as definições precisas próximas a ele. Portanto, eu recomendaria pessoalmente usar esse conteúdo externo de alta qualidade, em vez do conteúdo interno de média qualidade que eu poderia produzir. A resposta curta é: se você deseja apenas encontrar uma mediana aproximada, pode fazê-lo no tempo linear O (n).

user71641