# Automatic calculation of the intersection of discrete curves

first of all, let me apologize for a poor math-english translation, I'll try my very best.

I have the following situation: I have over 16.000 data files which I generated from a biometric verification system. Those files contain Error Rates for False-negative and False-positive at a specific threshold. So every data file becomes one Plot to detect an equal error rate (intersection of both rates). Special is in this case, that it may also contain more than one intersection, which is not typical but possible in this case.

I used to use gnuplot before to generate plots, but now the amount is a new level.

I can't watch every plot by myself which would take days. And it's for sure that lots of the files may not contain any intersection in the result.

Therefore I wonder if there is any possibility to calculate for each file the intersection(s) with MATLAB, Mathematica or anything else?

And after having calculated maybe generate a plot (preferred svg format but not important in this step) for that file so that I end up with only "useful" data files and plots with a fixed threshold.

I hope I could explain what my problem is and seeing forward for your ideas.

(Note: Both examples do not belong together, just choosed quickly and randomly from the files)

# Data file example:

> #k    NFA NIA NFR NEA FAR FRR
> #Alpha Vector 0 0 -1 0 0 0 -1 0 -1 0 0 -1
> 0.4   280.0   280.0   0.0 40.0    100 0
> 0.41  280.0   280.0   0.0 40.0    100 0
> 0.42  280.0   280.0   0.0 40.0    100 0
> 0.43  280.0   280.0   0.0 40.0    100 0
> 0.44  280.0   280.0   0.0 40.0    100 0
> 0.45  280.0   280.0   0.0 40.0    100 0
> 0.46  280.0   280.0   0.0 40.0    100 0
>
> # k is the threshold, FAR and FRR are 2 curves. k is on x-axis, value of FAR/FRR on y.


Example Plot:

I have no experience with matlab and just worked with wolframalpha mathematica during calculus at university. I study computer sciences in Germany, so ideas for scripting and co are also welcome and probably welcomed :-)

-
Just out of curiosity, why is it important to find equal error rates? And why do you call it intersection of "polynomials"? As I see it, you linearly interpolated the data points. – begeistzwerst Nov 23 '12 at 9:45
That's what gnuplot does with the datapoints. Normally, you wald have lots more of points so the linear line becomes more a curve. If I choosed wrong math definitions I am sorry, please correct me. It is important to find equal error rates in order to know how "good" the system works and which Alpha Vector (as comment in data file) achieves reasonable results. – Stefan Nov 23 '12 at 9:50
I am sorry, but I do not understand the connection between your data and your plot. And what is/does an alpha vector? Maybe you can rewrite it? But, to be sure, your problem is not a rare one. I am sure you can find code and documentation on intersection detection on the Matlab Central, for instance, (unless you want to find out on your own how to do it, of course). – begeistzwerst Nov 23 '12 at 10:07
As I mentioned, the datafile example and the plot do not belong together. Maybe I should mark the note strong. The alpha vector is not necessary to know for the question of detect intersection. It is necessary for me after I have the results. – Stefan Nov 23 '12 at 10:13

Let $k_1,\ldots, k_N$ be your points on the $x$-axis. Denote the two data sets you want to compare by $f_i := f(k_i)$ and $g_i := g(k_i)$.

First, it can happen that $f_i = g_i$ for some $i$. In this case you already found an intersection.

Second, you can have that $f_i > g_i$ and $f_{i+1} < g_{i+1}$ (or vice versa). This means that there is an intersection in the interval $(k_i, k_{i+1})$. Does this information suffice?

If not: Where exactly the point of intersection is located, depends on how you interpolate the data. The simplest type of interpolation is probably a linear one (as in your plot), in which case you only have to find the intersection of two lines. Can you do that?

-
This helps me a lot and I wonder why I couldn't think of such a simple parsing method of my files to sort out those, that don't have any intersection.. thank you! – Stefan Nov 23 '12 at 11:02
You are welcome. But I still think you should change the title of your question to a more appropriate one. Because what you are looking for is an intersection of discrete (interpolated) data. It would help people with the same problem to find this thread. Also (if you are new to this site), don't forget that you can accept an answer. – begeistzwerst Nov 23 '12 at 12:07
I just changed it myself. – begeistzwerst Nov 23 '12 at 12:22
Thank you for giving the question a more appropriate title. I will accept answers after a while to be sure no better answer is given after some time. I am not new to stackexchange, but new to mathexchange :-) Thank you anyhow for any advice :-) – Stefan Nov 23 '12 at 12:38