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 candidate intersection points $L$
In the next step this candidate list is taken to generate an undirected graph with nodes = $L$ and they are connected if $|p-q| < 2 \epsilon$. Consider the connected components of this graph and take the mean value of each connected component:
$$q_C = \frac{1}{|C|}\sum_{p \in C} p $$
Then the approximate list of self intersection points will be :
$$\{ q_C | C \text{ is connected component } \}$$
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 $N\cdot (N+1)/2$ times over the points?
Thanks for your help!
Edit: With the help of @PaulSinclair in his answer, I could find an algorithm which solves this question approximately:
One can use the Bentley-Ottmann algorithm after construction a polygon of the curve.
The answer to Q1 is no. As currently described, this will not always find intersection points. You choose $\epsilon$ to be the smallest gap beween adjacent vertices. But you don't do anything to limit how large the gaps are between other vertices.
For example, when $N = 5$, consider: $$\begin{align}P_0 &= (1,1)\\P_1 &= (-1, -1)\\P_2 &= (-1,1)\\P_3 &= (1,-1)\\P_4 &= (1,0)\\P_N &= (1,1)\end{align}$$
For this curve $\epsilon = 1$ and there are no vertices whose distance is less than that, so $L$ is empty and the rest falls apart.
So what about increasing $N$? One way you can do it is to repeatedly increase $N$ by $1$, with $P_N$ remaining as $(1,1)$, and filling the now vacated $P_{N-1}$ with the new point $\frac 12(P_N + P_{N-1})$. This halves the value of $\epsilon$ each time, but does not change the fact that none of the $P_i$ are in a distance $< \epsilon$ of each other. So no matter how large $N$ gets by this procedure, $L$ remains empty, and the intersection at $(0,0)$ is never found.
You'll have to control in some way the ratio of the largest gap to the smallest gap to guarantee that a limit point will be found.
Personally, once you polygonalized your curve, you are dealing with line segments. And figuring out exactly (up to computational accuracy) when and where two line segments intersect is not that hard to accomplish, so any additional approximation after the polygonalization does not seem worthwhile.