A sweepline algorithm to solve the two-center problem (Q1318733): Difference between revisions

Given a set \(N= \{p_ 1,p_ 2,\dots,p_ n\}\) of \(n\) points in the plane, the two-center problem is to allocate two circles such that all the points in \(N\) are covered by the two circles (each point is covered by at least one circle) and the radius of the bigger circle is minimized. In this paper, a sweepline algorithm has been proposed to solve the two- center problem with time complexity \(O(n^ 2\log n+ H(N))\); where \(H(N)\) is a function of the given point set \(N\) and \(H(N)\leq n^ 3\). The average case time complexity of the proposed algorithm is also analyzed. If the given \(n\) points are uniformly dispersed in a convex polygon, then we show that the proposed two-center algorithm has an expected time complexity \(O(n^ 2\log n)\).