mandeep
BAN USERIf for every point we create a map of the following structure :
<distance, count>
where distance is the distance of this point from another point in the plane. If two points A and B are equidistant from the same point P, then they must both lie on a circle with centre P and passing thru both these points A and B. The count gives us how many points are at a particular distance from point P.
Once we have computed this for every point, we then need to find the distance with maximum count. That point will be the centre and distance will be the radius.
In order to avoid repetitive updation for same set of points, we can update the hashtables of both points at the same time. For example, if we are calculating distance between A and B, we can update hashtables of A and B simultaneously.
I have not tested this yet but I think it should work. I hope I am not missing out anything.
- mandeep April 22, 2012