On Sat, 30 Dec 2006, sen1 at math.msu.edu wrote:
> 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 $$
Oops, forgot to put in $x(t),y(t)$ in these last equalities. This is
a given curve (maybe even a line segment).
> 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 |
---------------------------------------------------------------------------