¿Es posible calcular algorítmicamente la intersección de dos conjuntos semialgebraicos 2D? ¿Cuál es la peor complejidad del cómputo?

Answer 1

Respuesta de un amigo que pregunté fuera de Quora:

“Si desea calcular una representación de la intersección de dos conjuntos semi-algebraicos, simplemente tome la operación” Y “de ellos, ya que se definen como combinaciones booleanas de inecuaciones polinómicas, se cierran debajo de eso. Si desea Para calcular algunos puntos que se encuentran en la intersección, debe iterar sobre las posibles combinaciones de inecuaciones que pueden mantenerse de tal manera que se satisfaga la función booleana que representa el conjunto semialgebraico. Luego resuelva ese conjunto de inecuaciones. Puede, por ejemplo, traducir el inecuaciones a las ecuaciones mediante la introducción de variables ficticias y calcular la base de Grobner del conjunto resultante de ecuaciones polinómicas, que le ayuda a encontrar una asignación de este tipo “.

Luego seguí con: “¿Por qué, entonces, hay algoritmos dedicados a encontrar la intersección de polígonos no convexos? ¿No son también semialgebraicos?”

Su respuesta: “Supongo que es porque trabajar con conjuntos semialgebraicos generales parece ser muy costoso (la eliminación del cuantificador parece ser 2 EXPTIME). Los polígonos son mucho más simples e incluso encontrar la intersección de polígonos no convexos debería ser mucho más barato de 2EXPTIME “.

Answer 2

Esto básicamente se reduce a resolver un par de ecuaciones implícitas f ( x , y ) = 0 y g ( x , y ) = 0. Si uno de estos, g, es lineal ax + por + c = 0, puede sustituir y = ( ax + c ) / b y tener una ecuación en x del mismo grado que f . Si f tiene un grado inferior a 4, entonces hay disponible una solución analítica.

Siempre puede convertir una combinación de ecuaciones en una sola f ^ 2 + g ^ 2 = 0, dando una ecuación que duplica el grado máximo de f y g . Quizás esta no sea la forma más fácil de encontrar las soluciones.

Hay medios analíticos para resolver versiones de grado superior, que no recuerdo de inmediato.

Answer 3

Sí, la complejidad del peor de los casos es de hecho O (n ^ 2). Sin embargo, para optimizar esto, debe tener ambos conjuntos “ordenados” de manera práctica y sin datos redundantes.