¿Métodos o técnicas algorítmicas para encontrar conjunciones en grandes conjuntos de vectores de estado?

Supongamos que quisiera responder a la pregunta ¿ Pasará Starman/Roadster particularmente cerca de algún asteroide en los próximos años? o tratar de predecir conjunciones de satélites alrededor de la Tierra (por ejemplo, SOCRATES de Celestrak ), y tenía efemérides, TLE o tablas interpolables de vectores de estado.

Podría propagarlos en pequeños pasos de tiempo, calcular todos norte puestos y todo norte ( norte − 1 ) / 2 distancias y buscar cualquiera por debajo de una distancia d C o norte j , pero esa podría no ser la forma más eficiente de hacerlo.

Pregunta: ¿ Cuáles son los métodos o técnicas algorítmicas para hacer este tipo de búsqueda de manera más eficiente? Suponga que los propagadores devuelven un seis vector (posición y velocidad). Necesito una explicación o una referencia autorizada, no solo un nombre.

¿Esta pregunta es distinta de los métodos o técnicas algorítmicas para encontrar conjunciones en conjuntos de elementos keplerianos de alto N? porque pregunta específicamente sobre métodos que operan en vectores de estado (ya sea tabulados o propagados a pedido) que pueden incluir efectos de n-cuerpos (por ejemplo, el Sol se mueve, Júpiter hace lo suyo, etc.)

He decidido volver a hacer esta pregunta basándome en este consejo . Espero que vuele esta vez, en lugar de "conjuntar" (chocar) con su pregunta hermana .
Si entiendo correctamente que pregunta sobre el problema del par de puntos más cercano en el espacio euclidiano de seis dimensiones , entonces esta pregunta es lo suficientemente general como para adaptarse a Math.SE. ¿O especificas algo relacionado con la mecánica orbital?
¿Por qué te interesan las conjunciones de velocidades? Es decir, ¿por qué incluye las 3 dimensiones con la velocidad en el vector de estado? La pregunta original de Starman/Roadster se refiere únicamente a las posiciones.
@EverydayAstronaut una conjunción es cuando dos objetos alcanzan un punto similar en el espacio-tiempo 4D ( X C , y C , z C , t C ) . No he preguntado sobre las velocidades en t C . Sin embargo , para predecir si eso sucederá en algún momento en el futuro, necesita sus dos vectores de estado y dos épocas. ( X 1 , y 1 , z 1 , v X 1 , v y 1 , v z 1 , t 1 ) y ( X 2 , y 2 , z 2 , v X 2 , v y 2 , v z 2 , t 2 ) . Ese es el problema mínimo. Mi pregunta es sobre un conjunto de norte vectores de estado y épocas ( X i , y i , z i , v X i , v y i , v z i , t i ) y mirando O ( norte 2 ) pares y predictores de conjunciones para cada uno.
Pensé que tu sombrero norte estados ( X i , y i , z i , v X i , v y i , v z i ) y desea encontrar el par de puntos más cercano entre estos norte puntos en 6 dimensiones para cada punto discreto en el tiempo. Por favor, ayúdenme con esta configuración 4-D. ¿Qué tipo de métrica usas en ese espacio para este propósito? ¿Algo como Minkowski? Quiero decir que necesitas sopesar la distancia espacial y temporal.
@EverydayAstronaut si observa el enlace SÓCRATES en la pregunta: "Umbral de cálculo: 5,0 km" Entonces, si hay un momento en el que están a 5,0 km uno del otro (por ejemplo, una vez puede elegir otro número) entonces ha habido una conjunción .
Así que tratas de encontrar 2 puntos similares en el espacio exactamente al mismo tiempo. Para conjuntos de posiciones discretos en el tiempo (3D), este es definitivamente el problema de par de puntos más cercano. Si no encuentra ayuda aquí, le recomiendo Math.SE. Engineering.SE aún no tiene las etiquetas "mecánica de contacto" y "sistemas multicuerpo" :-(
@EverydayAstronaut No veo la palabra "exactamente" en ninguna parte; Acabo de mencionar "...dentro de 5,0 km uno del otro..." inmediatamente encima de su comentario. De todos modos, no estoy pidiendo que alguien me explique cómo hacer esto o resolver desde los primeros principios, estoy pidiendo referencias a algoritmos existentes específicos para la situación de un conjunto de órbitas enlazadas, propagándose en el campo gravitacional de la Tierra .

Respuestas (1)

Digamos que desea hacer algo "razonable", como recopilar conjunciones segundo a segundo durante un período de cien años, para todos los objetos que puede tener en sus manos en vectores de estado (¿cien mil o algo así?)

Tienes un O ( S ⋅ norte 2 ) acercarse, así que... sobre ≈ 10 20

Sí, puedo ver que hay un problema.

Para el sistema solar, las cosas se mueven a una velocidad limitada. Entonces podemos aprovechar el hecho de que los objetos solo pueden moverse hasta cierto punto en cada paso de tiempo.

Aquí hay un algoritmo de partición de tiempo:

  1. Explore toda su pila de datos de vectores de estado para encontrar la velocidad más alta. O ( S ⋅ norte ) . Ese debería ser un tiempo de ejecución aceptable, ya que ni siquiera podría almacenar todos esos vectores de estado si no fuera así.

Terminará con un caso extremo, como la velocidad del perihelio de 1566 Ícaro , del orden de ~100 km/s. Entonces, para el peor de los casos, la velocidad relativa, los objetos que se mueven directamente uno hacia el otro, podemos asumir un límite superior de aproximadamente ~ 200 km / s.

  1. Ahora, para cada objeto, uno a la vez:

Realice pasos de tiempo "aproximados", verificando la distancia a todos los demás objetos. Digamos, 10 días. Eso es seis órdenes de magnitud menos de trabajo que la granularidad que está buscando.

En esos 10 días, las distancias pueden cerrarse como máximo en ~1AU si las velocidades relativas pueden ser como máximo de 200 km/s.

Ahora, para los 10 pasos de tiempo "menos aproximados" entre 1 día, solo considere aquellos objetos dentro de 1 AU en el paso de tiempo "aproximado". Eso en muchos casos será una lista más corta.

Entre eso nuevamente, inserte 10 intervalos de tiempo "aún menos aproximados" de 2.4 horas. Aquí, solo tenemos que considerar aquellos dentro de 0.1 AU en el paso de tiempo "menos aproximado". Eso debería ser una pequeña minoría de su base de datos de vectores de estado.

En la granularidad de paso de tiempo de ~ 15 minutos, se redujo a ejecutar la lista corta de 0.01 AU. A los 1,5 min, 0,001 UA.

Si detiene la partición aquí, solo habrá un par de objetos (¡o ninguno!) para verificar en cada paso de tiempo.

Para objetos distribuidos en un volumen, o incluso agrupados a lo largo de un solo plano 2D, esto es asintóticamente O ( norte 2 ) . Es decir, no tiene que preocuparse por limitar la granularidad de sus pasos de tiempo.

Incluso para el agrupamiento lineal muy desagradable (que, por cierto, no se aplica a los objetos del sistema solar), esto sigue siendo el peor O ( yo o gramo ( S ) ⋅ norte 2 )

Debería poder examinar la pila en un par de minutos en una computadora portátil de esta manera.

¿Métodos o técnicas algorítmicas para encontrar conjunciones en grandes conjuntos de vectores de estado?
RespuestasAquíPolítica de privacidad1y, 0v