3
$\begingroup$

Consider a (smooth) function \begin{align*} F: \mathbb{R}^2 \to \mathbb{R} \end{align*} with the contour
\begin{align*} \mathcal{C} = \{x \in \mathbb{R}^2 | F(x) = 0\} \end{align*} The function (and possibly derivatives) will be given as analytical expression, and be continuously differentiable everywhere. I am trying to find an algorithm that takes two points $x_1, x_2 \in \mathcal{C}$ that are numerical roots of this function and tells me, if they lie on the same connected component of $\mathcal{C}$ (or maybe some more general set). I am a little lost here. I found some info on a (pretty complicated) algorithm that seemingly would allow me to first construct a graph representing $\mathcal{C}$ with accurate topology, and then I could just check to which connected component my points belong.

However, I don't fully understand the algorithm and it seems a little overboard for what I want to do. Does anyone know of an easier/faster algorithm to achieve this? Will I have to compute the full contour to solve this?

Edit: In case I really have to compute the full contours (or at least trace part of them) and there is no shortcut, my question would be: How can I compute the connected components of the contour? All sources I stumble upon already require me having a graph that encapsulates the correct connectedness informations and tracing seems problematic without any reliable "test" to find out if two points (e.g. one before and after some tracing step) are indeed on the same component. Ideally I would like an algorithm that constructs a function, say $G:\mathcal{C} \to \mathbb{R}$, such that $G(a)=G(b)$ iff $a$ and $b$ lie on the same connected component.

$\endgroup$
  • $\begingroup$ How is $F$ provided? Do you have an analytical expression for $F$, or are you just given a black box (oracle) that lets you evaluate $F$ on any point? Are you able to compute the gradient of $F$? Do you have an analytical expression for the gradient of $F$? Is $F$ continuously differentiable everywhere? $\endgroup$ – D.W. Feb 20 '18 at 18:07
  • $\begingroup$ In my specific case, $F$ (and all derivatives) will have an analytical expression and be continuously differentiable everywhere $\endgroup$ – Banana Feb 21 '18 at 1:10
  • $\begingroup$ Cool. Can you incorporate that information into the question? $\endgroup$ – D.W. Feb 21 '18 at 1:45
2
$\begingroup$

If $F$ is continuously differentiable and smooth, you can use the gradient to walk along the contour. In this way you could walk on the contour starting at $x_1$ (tracing both directions of the contour) and see if you reach $x_2$.

In particular, if you're currently at a point $x \in \mathcal{C}$ on the contour, then the gradient $\nabla F(x)$ tells you what direction to walk if you want to stay on the contour: you should walk in the direction $(\nabla F(x))^\perp$, where we define $(a,b)^\perp = (b,-a)$. (In other words, you should walk in the direction perpendicular to the gradient.) In particular, when $\epsilon$ is sufficiently small, $x + \epsilon \cdot (\nabla F(x))^\perp$ will be approximately on the contour. This is because $\nabla F(x)$ points in the direction that most increases $F$, and if we're on a contour and the contour is a line, $\nabla F(x)$ points in a direction perpendicular to that contour. (See, e.g., https://math.stackexchange.com/q/599488/14578.)

So in principle if the contour was a simple line (whether closed or open), the following would be sufficient: start at $x_1$ and walk in one direction and see if you eventually reach $x_1$. In parallel, start at $x_2$ and walk in the other direction and see if you eventually reach $x_2$.

In practice there are two complications.

First, the contour is curved, so the gradient only helps you walk in a direction that is approximately along the contour -- but maybe not exactly. So, I suggest a refined way to walk at the contour. At you're currently at the point $x$, first to the point $x' = x + \epsilon \cdot (\nabla F(x))^\perp$. The point $x'$ might not be exactly on the contour, but it'll probably be close. Next, use gradient descent starting at $x'$ to find a point on the contour that is close to $x'$. If $F$ is everywhere positive, you might do this by minimizing the objective function $\Phi(x'') = F(x'') + c \cdot \|x''-x'\|^2$ where $c>0$ is a sufficiently small constant; otherwise, you can use $\Phi(x'') = F(x'')^2 + c \cdot \|x''-x'\|^2$. If you have a better way to find the nearest point on the contour, go ahead nad use that. Finally, walk to this point $x''$. This gives you an adjacent point on the contour, that's approximately distance $\epsilon$ away from where you started. Repeat this.

The second complication is that the contour might not be a simple line; there might be places where two or more lines meet at an intersection. At this point, $F$ won't be differentiable and the gradient might not be computable or meaningful. You'll have to figure out how to detect that situation; perhaps you can use your domain knowledge about $F$ to help you detect that. If you have no other ideas, one possibility is to pick a dozen random points in the neighborhood of $x$, project each one to the nearest point on the contour, check the gradient, and see if all of them seen consistent with a single nearly-straight line or whether their appear to be multiple lines converging. Once you detect an intersection point, you can use depth-first search (basically, explore all directions out of the intersection point) to traverse the connected component -- then it reduces to the problem of checking whether two vertices in an undirected graph are in the same connected component, and that can be done using DFS.

This uses techniques that are quite similar to that proposed in my answer to your previous question on a 3D version of this situation.

$\endgroup$
  • $\begingroup$ thanks for your elaborate answer as always :) I actually thought I might be able to use your answer to my previous question, but had some problems with that (probably should've mentioned). Firstly, choosing $\epsilon$. If it's too small, the calculations become long (evaluating function and gradient repeatedly) and inefficient. Secondly, I found the minimizing (to go back to the contour) problematic - I tried another gradient descent, only works if the point is really close to the contour (i.e. $\epsilon$ small). Lastly, when two components are close, I might jump and have no way of knowing. $\endgroup$ – Banana Feb 21 '18 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.