OK,
Here is the real mathematical problem.
I have two polynomial maps $F_1(x,y), F_2(x,y)$ from the plane to the
plane. They have low degree, say 2 for now.
Given numbers $a > 1, b > 1$, I compute parametrized curves
$C_1(t,n), C_2(t,n)$ which have the form
$$ C_i(t,n) = (F_i)^n (a^(-n)*x, b^(-n)*y), \ i = 1,2 $$
Here $F_i^n$ is the $nth$ iterate of $F_i$, so it has degree $2^n$.
In the actual mathematical problem at hand, it seems that most of the
coefficients of the polynomial iterates $F_i^n$ are small. From
numerical calculations, it seems that Only about 10 or
12 are significant.
I am interested in computing the intersections of the curves
$C_1(t,n), C_2(t,n)$ in the unit square for $n=12$.
Bezout's estimate gives a (very crude) upper bound for the number of
intersections of $2^{24}$. In my case, for other reasons, the actual
number intersections is likely to be around 500. I want to find all
(or most ) of these intersections.
So, what is the best tool?
I found a package on CGAL which is called (something like "2d
Arrangements") which is written in C++. This uses some sort of
"sweepout algorithms" to find the intersections of curves. I haven't
yet implemented it.
Given this kind of problem, is it a waste of time to try to use
maxima?
Thanks for any suggestions.
-sen
On Sat, 30 Dec 2006, Richard Fateman wrote:
>
>
>> -----Original Message-----
>> From: maxima-bounces at math.utexas.edu
>> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of sen1 at math.msu.edu
>> Sent: Saturday, December 30, 2006 8:11 AM
>
> ...
>
>
>>>
>>> For searching, a bipartition method could be fast enough:
>> first compare
>>> x with element in position length(z)/2, and take the inferior or
>>> superior half of pairs, and repeat this process until you find the
>>> interval.
>>>
>>> Does this help?
>>
>
> A suggestion, if this is to be fast, storing the elements in a LIST is a bad
> idea, because to get the element in position L takes L steps. This converts
> a fast method (binary search which takes logarithmic time) into linear time.
> If you want to do linear time, just iterate down the list searching for the
> right interval in order.
>
> Allocating a proper array and sorting it is very easy in lisp; it can't be
> too hard in maxima.
> On the other hand, the linear time search might be so fast that you don't
> really need to do binary search at all.
>
> I don't know what the objective really is here, but there are lots of
> geometric computation packages, and I have recently looked at a
> computational vision package (associated with another version of lisp, LUSH)
> with lots of tools that probably include more general stuff than this, at
> least for numerical inputs.
>
>
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
--
---------------------------------------------------------------------------
| Sheldon E. Newhouse | e-mail: sen1 at math.msu.edu |
| Mathematics Department | |
| Michigan State University | telephone: 517-355-9684 |
| E. Lansing, MI 48824-1027 USA | FAX: 517-432-1562 |
---------------------------------------------------------------------------