¿Cómo encontrar dos puntos más distantes?

Question

Esta es una pregunta que me pidieron en una entrevista de trabajo hace algún tiempo. Y todavía no puedo encontrar una respuesta sensata.

La pregunta es:

se le da conjunto de puntos (x, y). Encuentra 2 puntos más distantes. Distante el uno del otro.

Por ejemplo, para los puntos: (0,0), (1,1), (-8, 5) - los más distantes son: (1,1) y (-8,5) porque la distancia entre ellos son más grandes de ambos (0,0) - (1,1) y (0,0) - (- 8,5).

El enfoque obvio es calcular todas las distancias entre todos los puntos y encontrar el máximo. El problema es que es O (n^2), lo que hace que sea prohibitivamente costoso para grandes conjuntos de datos.

Hay un acercamiento con los primeros puntos de seguimiento que están en el límite, y luego calcular distancias para ellos, bajo la premisa de que habrá menos puntos en el límite que "adentro", pero sigue siendo costoso y fallará en el peor de los casos.

Intenté buscar en la Web, pero no encontré ninguna respuesta sensata, aunque esto podría ser simplemente mi falta de habilidades de búsqueda.

Answer 1

EDIT: Una forma es encontrar el casco convexo http://en.wikipedia.org/wiki/Convex_hull del conjunto de puntos y luego los dos puntos distantes son vértices de esto.

Posiblemente contestadas aquí: Algorithm to find two points furthest away from each other

también:

• http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

Answer 2

Algoritmos de punto de frontera abundan (busque algoritmos de casco convexo). A partir de ahí, debería tomar O (N) el tiempo para encontrar los puntos opuestos más distantes.

Del comentario del autor: primero encuentre cualquier par de puntos opuestos en el casco, y luego camine alrededor de él en modo semicerrado. Dependiendo de los ángulos entre los bordes, tendrá que avanzar ya sea un andador o el otro, pero siempre tomará O (N) para circunnavegar el casco.

Answer 3

A pocos pensamientos:

lo podría hacer en sólo los puntos que definen la envolvente convexa de su conjunto de puntos para reducir el número, ... pero todavía se ve un poco "no es óptima".

De lo contrario, puede haber un enfoque recursivo quad/oct-tree para unir rápidamente algunas distancias entre conjuntos de puntos y eliminar grandes partes de sus datos.

Answer 4

Un punto de partida podría estar buscando problemas en el más cercano de punto, que han sido examinadas.Wikipedia enumera algunas opciones:

http://en.wikipedia.org/wiki/Closest_point_query

Answer 5

Un algoritmo estocástico para encontrar el par más distante sería

• elegir un punto al azar
• Obtener el punto más lejano a él
• Repetir una pocas veces
• Eliminar todos los puntos visitados
• Elegir otra r punto aleatorio y repetir algunas veces.

Usted está en O (n) siempre y cuando predetermine "algunas veces", pero no se garantiza que realmente encuentre el par más distante. Pero dependiendo de tu conjunto de puntos, el resultado debería ser bastante bueno. =)

Answer 6

Esta pregunta se presenta en Introducción al algoritmo. Mencionó 1) Calcular casco convexo O (NlgN). 2) Si hay M vectex en Convex Hull. Entonces necesitamos O (M) para encontrar el par más lejano.

Encuentro estos enlaces útiles. Incluye análisis de detalles de algoritmo y programa. http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html

Deseo que sea útil.

Answer 7

Está buscando un algoritmo para calcular el diámetro de un conjunto de puntos, Diam (S). Se puede demostrar que este es el mismo que el diámetro del casco convexo de S, Diam (S) = Diam (CH (S)). Así que primero calcule el casco convexo del conjunto.

Ahora tiene que encontrar todos los puntos antipodales en el casco convexo y recoger el par con la distancia máxima. Hay O (n) puntos antipodales en un polígono convexo. Por lo tanto, esto proporciona un algoritmo O (n lg n) para encontrar los puntos más lejanos.

Esta técnica se conoce como Pinzas giratorias. Esto es lo que Marcelo Cantos describe en su respuesta.

Si escribe el algoritmo con cuidado, puede hacerlo sin calcular los ángulos. Para obtener más información, consulte este URL.

Answer 8

Esto parece fácil si los puntos se dan en coordenadas cartesianas. Tan fácil que estoy bastante seguro de que estoy pasando por alto algo. ¡Siéntase libre de señalar lo que me estoy perdiendo!

1. Encuentra los puntos con los valores máximo y mínimo de sus coordenadas x, y, z (6 puntos en total). Estos deberían ser los puntos más "remotos" de todos los límites.
2. calcular todas las distancias (30 distancias únicas)
3. encontrar la distancia máxima
4. Los dos puntos que corresponden a esta distancia máxima son los que usted está buscando.

Answer 9

Dado un conjunto de puntos {(x1, y1), (x2, y2) ... (xn, yn)} encuentre 2 puntos más distantes.

Mi enfoque:

1). Necesita un punto de referencia (xa, ya), y será:
xa = (x1 + x2 + ... + xn)/n
ya = (y1 + y2 + ... + yn)/n

2). Calcule toda la distancia desde el punto (xa, ya) hasta (x1, y1), (x2, y2), ... (xn, yn)
El primer "punto más distante" (xb, yb) es el que tiene el distancia máxima

3). Calcule toda la distancia desde el punto (xb, yb) hasta (x1, y1), (x2, y2), ... (xn, yn)
El otro "punto más distante" (xc, yc) es el que tiene el distancia máxima

por lo que tiene sus puntos más distantes (xb, yb) (xc, yc) en O (n)

Por ejemplo, para los puntos: (0,0), (1,1), (- 8, 5)

1). Punto de referencia (xa, ya) = (-2.333, 2)

2). Calcular distancia:
desde (-2.333, 2) hasta (0.0): 3.073
desde (-2.333, 2) hasta (1,1): 3.480
desde (-2.333, 2) hasta (-8 , 5): 6.411
Así que el primer punto más distante es (-8, 5)

3). Calcular distancias:
desde (-8, 5) hasta (0,0): 9.434
desde (-8, 5) hasta (1,1): 9.849
desde (-8, 5) hasta (-8 , 5): 0
Así que el otro punto más distante es (1, 1)

Answer 10

vistazo a triángulos de ángulo recto A- (x1, y1), B- (x2, y2) y la distancia b/w A y B es = sqrt [(| x1 | + | x2 |)^2 + (| y1 | + | y2 |)^2]

Answer 11

Calcula la media de todos los puntos, mide la diferencia entre todos los puntos y la media, toma el punto la distancia más grande de la media y encuentra el punto más alejado de ella. Esos puntos serán las esquinas absolutas del casco convexo y los dos puntos más distantes. Hace poco hice esto para un proyecto que necesitaba cascos convexos confinados a planos infinitos dirigidos al azar. Funcionó muy bien.