[mattheww]

Hough transform is basically useless for precision tracking in a high multiplicity environment. Tracks have 5 degrees of freedom, so the memory costs make it infeasible. I think ATLAS uses it in the trigger, where you don't need to actually reconstruct all tracks, just find out if there are a couple passing certain criteria.

[danbruc]

You don't have to accumulate the transformation result into an actual five dimensional array, you can just transform the points, keep them in a list, a quad tree, or whatever you like, and then just run a clustering algorithm on the transformed points. Probably complicated by the fact that every point can vote for several parameters so that you are not actually clustering points but something like lines or planes associated with the points.

That seems also to be - but I did not look at the code - more or less what the creators of the challenge implemented and submitted as a benchmark implementation, admittedly with the expected poor performance score of only about 20 %.

[mattheww]

If you know a way to find clusters of intersections of hyperplanes, I'm pretty sure you can get a highly acclaimed paper out of it, but that is not what a Hough transform is. The Hough transform is an approximate solution to that problem which works by sampling the hyperplanes and then polling them. There's no way to perform a Hough transform without having many more transformed points than input points, and the more precision you need, the more points you need.

[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.