# Detecting isthmuses on digital curves

Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them.

I want to find the isthmuses, i.e. sections of the curve that are close to each other (within a fixed threshold), though the indexes ("curvilinear" abscissa) differ by a large amount. For a curve of length $L$, there are $O(L^2)$ inter-pixel differences, but the size of the answer does not exceed $O(L)$.

Can you advise an efficient procedure ? Update:

I believe that the following approach might be effective: we can sort the points on their $x$ abscissa using histogram sort, in time $\Theta(L)$, while keeping the corresponding index with them. Then for any point $(x_0,y_0)$, the possible close neighbors are found in the range $x_0-D\le x\le x_0+D$.

Assuming that a vertical line hits the curve $I$ times on average (for ordinary curves, $I$ will be a little more than $2$), the total effort will be at worse $O(LDI)$. Given that the intersections are found on the curves and change little from column to column, I suspect that by some incremental process, the dependency on $D$ could be lowered. Maybe also an auxiliary sort on $y$ can help.

You should probably do this do this four times: once with the original grid; again with that grid moved by one-half to the right; again with it moved one-half down; and again with it moved one-half to the right and one-half down. If you use grid cells of side length $2D$, then this ensures that if the distance of the isthmus is $\le D$, it will be detected during one of these four iterations.
• Interesting. Notice that $L$ is not the distance threshold (say $D$) but the curve length. The grid size should be on the order of $D$. If one considers a section the curve contained in a grid cell, the possible neighbors are found in a $3\times3$ block of cells. For constant $D$, this seems to yield an $O(L)$ procedure. Jul 1, 2018 at 20:21