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 ?

enter image description here


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.


1 Answer 1


Divide the image up into evenly sized grid cells. Have one hash bucket per grid cell, and hash each point on the curve into the grid cell it falls in. Sort all of the elements in each grid cell / bucket by the order of their abscissa. Then, you can iterate over all of the non-empty grid cells, and for each, iterate over their sorted list to look for an instance of a large gap. Each isthmus will correspond to a pair of adjacent elements in the sorted list that have a large difference in their abscissa.

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.

  • $\begingroup$ 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. $\endgroup$
    – user16034
    Jul 1, 2018 at 20:21
  • $\begingroup$ @YvesDaoust, oops, I should have used a different letter. Sorry about that. I just made a revision. $\endgroup$
    – D.W.
    Jul 1, 2018 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.