Trova la distanza massima tra 5 punti separati

Question

Diciamo che mi vengono dati 5 punti separati, sul piano delle coordinate.

Come faccio a trovare la distanza massima tra un punto e l'altro?

Quello che intendo non è la distanza tra 2 punti, ma voglio passare attraverso ogni punto e trovare la distanza massima.

C'è 1 semplice formula per farlo? Spero di essere chiaro.

Answer 1

Sebbene non esista un algoritmo efficiente noto (vedere il commento di Doug M), ci sono modi più semplici per risolverlo che trovare la distanza euclidea. In particolare, utilizziamo le seguenti proprietà della norma:

Permettere $d^p_{i,j}$ essere la distanza p-norm tra i punti $i$ e $j$(se vuoi essere tecnico, è la p-norma del vettore formato sottraendo quei due punti). Dal momento che non posso dimostrarlo in generale, limitiamo p a 1 o 2. Quindi, se, per un dato$i,j$ e un arbitrario $p$, $d^p_{i,j}$ è massimo, quindi è massimo per tutti $p$.

In pratica, questo significa che possiamo calcolare la norma 1, che è molto più semplice. La norma 1 sarebbe solo:

$$d^1_{i,j} = |x_i-x_j| + |y_i - y_j|$$

Quindi computazionalmente devi fare due sottrazioni e potenzialmente una negazione e una somma, piuttosto che (con la norma 2), due sottrazioni, un quadrato, una somma e una radice quadrata.

Cerca la 1-norma più alta, quindi calcola solo una singola 2-norma.

Answer 2

Questo è attualmente un problema aperto, TSP massimo euclideo planare .

Esiste un algoritmo tempo lineare ottimale per $\mathbb{R}^2$ con il $L_1$-norm (vedi Teorema 3 da [1]).

Il TSP massimo è noto per NP-difficile $\mathbb{R}^3$ con la norma euclidea (vedi Teorema 4 da [1]).

[1]: The Geometric Maximum Travelling Salesman Problem ( arxiv )

---

In alternativa, potresti chiedere il diametro di un insieme di punti planare.

In questo caso, le pinze rotanti forniscono un ottimale$O(n \log n)$ algoritmo.

Per velocizzare i confronti individuali, è possibile utilizzare la norma euclidea quadrata.