Looking for an efficient algorithm to detect Tomek links

I'm looking for an efficient algorithm to detect Tomek links. I'm wondering if anyone knows where to find it.

This is the definition of Tomek links: Suppose $\{ E_1,\ldots,E_n\} \subset R^k$ is a dataset, with each $E_i$ having exactly one of two labels $+$ or $-$. A pair $(E_i,E_j)$ is called a Tomek link if $E_i$ and $E_j$ have different labels, and there is not an $E_l$ such that $d(E_i,E_l) < d(E_i,E_j)$ or $d(E_j,E_l) < d(E_i,E_j)$, where $d(x,y)$ is the distance between $x$ and $y$.

Thanks!

• could you please provide the definition of Tomek links ? I found one (citeseerx.ist.psu.edu/viewdoc/…), but I do not have access to the original source hence I was hesitating to modify the answer. Providing the definition can stimulate more answers, the name is somehow an obfuscation. – steffen Apr 29 '12 at 12:00
• Hi @steffen. Thanks for your suggestion. I added the definition. – user765195 Apr 30 '12 at 4:41