# algorithms – Approximately finding self intersection points of closed plane curves?

Let $$0 = t_0 < t_1 < t_2 < cdots < t_N = 2 pi$$.
I compute the points on the closed curve $$F(t)$$ in the complex plane , (Set $$epsilon = +infty$$) :

$$P_i = F(t_i)$$
$$P_{i+1} = F(t_{i+1})$$
if $$|P_i – P_{i+1}| < epsilon$$: then set $$epsilon := |P_i – P_{i+1}|$$.

In the next step I consider circles around those points on the curve of radius $$epsilon/2$$

Let $$L = {}$$

for $$i,j$$ in $$0,1,2,…,N, i neq j$$:

if $$| P_i – P_j | < epsilon$$: then add $$Q = (P_i+P_j)/2$$ to the list of intersection points $$L$$

This method seems to approximately work on some curves if $$N$$ is a large number:

Example (Please wait a few seconds for the plot to show up.)

Q1) Is it possible to prove, that this method will always find the intersection points if $$N$$ goes to infinity?

Q2) What better way would you suggest in the second step when testing if the circles overlap, instead of iterating $$Ncdot (N+1)/2$$ times over the points?