Find centre of circle with maximum point enclosed

Asked Jan 11 '17 at 09:47

Active Jan 11 '17 at 09:47

Viewed 726 times

I am giving a circle of radius R and N points on x-y plan , I want to draw a circle of radius R such that it maximize the number of points enclosed.

My Approach: If there exists a circle C that encloses M points, then by slightly moving C it will touch at least two points.

So, essentially we just need to check all circles which touch (at least) 2 points:

For each pair of points in the given set, construct a circle with radius R that touches both points. For each point pair there are at most two such circles.
For each constructed circle, check for each of the given points is inside it. Return the circle that encloses the maximum number of points.

Time Complexity O(N^3)

Is there any algorithm which i can reduce my time complexity ?

asked Jan 11 '17 at 09:47

Narendra Modi

http://stackoverflow.com/questions/2151162/find-the-most-points-enclosed-in-a-fixed-size-circle – Dmitry Bychenko Jan 11 '17 at 10:15
2

https://www.quora.com/What-is-an-algorithm-for-enclosing-the-maximum-number-of-points-in-a-2-D-plane-with-a-fixed-radius-circle – Dmitry Bychenko Jan 11 '17 at 10:16
1

This is not exactly your approach, this is a well known approach. – Saeed Amiri Jan 11 '17 at 11:24

Find centre of circle with maximum point enclosed

0 Answers0