3 ms·

>"In the new problem, she says, you have to find in the 100,000 points something like 10,000 arcs of ellipse." Does anyone know how long this currently takes?

• danbruc 8y ago
  That certainly depends on the amount of computing power you can throw at it and what level of accuracy you are trying to achieve. But the most naive attempt using a Hough transformation will probably take a couple of milliseconds on your average computer. However, the accuracy will be far from good enough with such a simple approach. I have no idea what amount of time state of the art algorithms will use, but I could well imagine that it is essentially a tunable parameter that is chosen to get the best accuracy given the amount of data you have to process and the time available to complete the task.
  • mattheww 8y ago
    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 8y ago
      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 8y ago
        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 8y ago
          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.
• mattheww 8y ago
  Depends exactly how you limit the problem, but going from detector hits to abstract arcs takes a few seconds.