A counter-example

ALIAS-Maple is designed to help generating C++ code and improving the efficiency of the algorithm. But it will not solve all the problems that may be treated by interval analysis as illustrated by the following example that originated from the Geometrica project.

Consider 2 ellipses E1, E2 in the plane that are perfectly defined and the
so-called *bi-tangent* i.e. the lines that are tangent to both
ellipsis. There is 4 such lines but we assume that some criteria
allows to choose two bi-tangents L1, L2. L1 intersects E1 at point P,
E2 at and L2 intersects E1 at point R and E2 at point S. We construct
now the vectors **PQ**, **RS** and then the determinant
D=**PQ** **RS**. The problem is to determine the sign of D in a
guaranteed manner (this sign is then used for another algorithm and a
mistake in the sign has a very negative influence).

A classical approach to solve this problem is to consider that the 8 coordinates of the points P, Q, R, S are the unknowns, write 8 equations to determine these unknowns, solve the system and then determine the sign of D. But this approach has drawbacks:

- the system of equations is complex
- it is difficult to solve
*exactly*

Now we may note that the coordinates of the points are bounded as the points are included in the bounding box of the ellipses. Being given ranges for the unknowns we may compute the interval evaluation of the determinant. If the lower bound is positive or the upper bound is negative we may directly state the sign of the determinant. If not we bisect one the unknown coordinates: we has thus a list of boxes with 8 ranges in each box, one for each coordinate. For each box we check if the coordinates ranges allows the points P, Q, R, S to belong to the ellipsis and to the bi-tangents, otherwise we reject the box. Then we compute the interval evaluation of D: if the lower bound is positive we store the box in a special array of boxes, called the positive array and discard it from the list. Similarly if the upper bound is negative we store the box in the negative array and discard it from the list. When the list of boxes is exhausted we look at the number of elements in the positive and negative array: if one array has 0 element, then we have determined the sign of D. Otherwise we consider the array that has the lowest number of elements and restart the bisection procedure on this new list, eliminating boxes that do not describe points on the ellipsis or that are not on the bi-tangent. At the end of this process we may have eliminated all the boxes of the list or, in the worst case, we will have computed the coordinates of P, Q, R, S i.e. we will end up with the classical approach. Our test show however that this is seldom the case and the above procedure is much more faster than solving using the classical approach.

Still in some cases the sign of D cannot be safely computed: this may happen for example when some coordinates have very large values while other have very small one. Numerical round-off errors then prohibit the exact determination of the sign of D, a fact that is detected by interval analysis. But we may still in some cases solve the problem: for that purpose instead of using Cartesian coordinates we may use polar coordinates with different ranges for the unknowns in the determinant or we may use an extended arithmetic. In any case the algorithm is safe as it provides either a sign, which is guaranteed, or will state that the sign cannot be determined with the current arithmetic.

In this example the `MakeF, MakeJ` procedures may be used to
generate the C++ code for evaluating the value of D and to check if
the points belong to the ellipsis. But then specific C++ code should
be written, mostly based on the ALIAS-C++ library.