El problema de la separación de elipses y elipsoides: una aplicación de la eliminación de cuantificadores

Abstract

RESUMEN: En este trabajo se derivan fórmulas para caracterizar cuando dos elipses o dos elipsoides se superponen, tienen un contacto tangencial externo o están separados por una recta o un plano, respectivamente. Esta cuestión aparece de forma natural en la resolución de problemas en tratamiento de imágenes, robótica, modelización, etc. Esto es debido a que es muy sencillo modelar distintos tipos de objetos mediante elipses y elipsoides. Sean A y B dos elipses o dos elipsoides definidas respectivamente por medio de sus matrices asociadas XTAX = 0 y XTBX = 0. En este trabajo se analizan los resultados en \W. Wang, J. Wang, M.-S. Kim: An algebraic condition for the separation of two ellipsoids. Computer Aided Geometric Design 18, 531-539, 2001"que caracterizan la posición relativa de dos elipsoides en funcion del signo de las raíces reales del polinomio f(λ) = det(λA + B), se extienden al caso de elipses y, usando las técnicas de eliminación de cuantificadores presentadas en \J. Caravantes, L. Gonzalez-Vega: On the Interference Problem for Ellipsoids: Experiments and Applications, Lecture Notes in Computer Science 10931, 89-97, 2018", se caracteriza dicha posición relativa en función de las entradas de las matrices A y B. De esta forma se determina la posición relativa de A y B sin tener que calcular los puntos de intersección entre ambos objetos y solo es necesario evaluar las fórmulas antes mencionadas. Este trabajo incluye también una experimentación en Maple donde se muestra como funcionan las fórmulas obtenidas para determinar cuando dos elipses o dos elipsoides, en movimiento, están separados por una recta o por un plano, respectivamente.

ABSTRACT: In this work, several formulas are derived to characterise when two ellipses or two ellipsoids overlap, have an external tangential contact or are separated by a line or a plane, respectively. This problem appears naturally in the resolution of problems in image processing, robotics, modeling, etc. because it is very easy to model different types of objects by using ellipses and ellipsoids. Let A and B two ellipses or two ellipsoids defined respectively by means of their associated matrices XTAX = 0 and XTBX = 0. In this work we analyse the results in \W. Wang, J. Wang, M.-S. Kim: An algebraic condition for the separation of two ellipsoids. Computer Aided Geometric Design 18, 531-539, 2001"that characterise the relative position of two ellipsoids in terms of the sign of the real roots of the polynomial f(λ) = det(λA + B), they are extended to the case of ellipses and, using the quantifier elimination techniques presented in \ J. Caravantes, L. Gonzalez-Vega: On the Interference Problem for Ellipsoids: Experiments and Applications, Lecture Notes in Computer Science 10931, 89-97, 2018", the relative position is characterised in terms of the entries of A and B. In this way, the relative position of A and B is determined without computing the points of intersection between both objects and it is only necessary to evaluate the aforementioned formulas. This work also includes an experimentation in Maple showing how the obtained formulas can be used to determine when two moving ellipses or two moving ellipsoids are separated by a line or a plane, respectively.