On Sat, Dec 30, 2006 at 03:55:01PM -0500, sen1 at math.msu.edu wrote:
> OK,
> Here is the real mathematical problem.
...>
> 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$.
> So, what is the best tool?
This is a very good example of a mathematical problem where maxima can
do symbolic calculations for you, and then you need numerical results
and find yourself with the choice: do I continue in maxima or do I
move my symbolic results to some other more numerically oriented tool?
I tend to think that for this problem you're better off staying in
maxima, but you may need some special code.
Of course, if you can come up with some mathematics to help you it
will be advantageous, but here are some computational ideas for
finding the intersections:
divide the unit square into n by n subsquares. Now divide the range of
the parameter t into k subunits. For each of the k values of t (at the
center of each of the k intervals) for each of the curves c_i, compute
which of the squares each of the curves is in. Store in an nxn array a
list of what values of t and for which curves the curve was in which
subsquare (that is poorly worded, but hopefully you understand the
principle which is to localize the curve to a box on a given interval
of t)
Now you can look at each non-empty subsquare for matching pairs t1 and
t2 so that c1(t1) and c2(t2) are both in the same subsquare. Now you
should be able to linearize or taylor approximate over the interval
associated with t1 and t2 to solve for approximate intersections if any.
The result is that you now have k^2 pairs of intervals of the
parameter t to choose from (worst case), but hopefully using the nxn
grid to identify likely pairs of intervals you are able to limit your
search to considerably less than all of the k^2 pairs of intervals.
I think using a 2d array of lists in maxima you would be able to
program this in 50 to 100 lines of code.
There are some technical issues that I'm sure you can see will come
up. It seems there will be a balance between k and n, it will be
advantageous to increase k so that the t intervals are small and the
curve is relatively linear over the intervals, but in order to do so
you will want to increase n in order to reduce the number of interval
pairs that need to be considered.
hope this helps.
Dan
--
Daniel Lakeland
dlakelan at street-artists.org
http://www.street-artists.org/~dlakelan