[danbruc]

I see, they actually did two different implementation, one DBSCAN based clustering approach, one based on a Hough transformation, and submitted the former one as a benchmark.

Not withstanding that, I am not yet convinced that a Hough transformation combined with something similar to a quad tree could not work. More specifically I am thinking of delaying the creation of votes. Roughly the first point just becomes a node in the tree corresponding to the bounding box of its entire possible parameter space. Only when we encounter a second point whose possible parameter space overlaps with that of the first one we split up the two volumes into one volume for which both points vote and a few volumes for which only one of the points vote.

This obviously requires that the possible parameter spaces do not have terrible shapes that are hard to bound and I also could see nearly perfectly overlapping volumes cause issues due to the generation of many small volumes for the imperfection in the overlap. There are probably more issues and possibly even show stoppers, but without picking up a pencil and really thinking about it, I not really tell whether or not it could work out. But, as said, I am also unable to see immediately why this could never work.