A Novel Approximation Algorithm for Max-Covering Circle Problem

We study the efficient approximation algorithm for max-covering circle problem. Given a set of weighted points in the plane and a circle with specified size, max-covering circle problem is to find the proper place where the center of the circle is located so that the total weight of the points covered by the circle is maximized. Our core approach is to approximate the circle with a symmetrical rectilinear polygon (SRP). We first present a method to construct the circumscribed SRP of a given circle and disclose their area relationship. Then, we convert max-covering SRP problem to SRP intersection problem, which can be efficiently solved with simple partition and modification based on the existing method. Finally, the optimal solution returned from max-covering SRP problem can be used to produce an approximate answer to max-covering circle problem. We prove that for most of the inputs, our algorithm can give a \(\left( 1-\varepsilon \right) \) approximation to the optimal solution, which only needs \(O\left( n\varepsilon ^{-1}\mathrm{{log}}\,n+n\varepsilon ^{-1}\log \left( \frac{1}{\varepsilon }\right) \right) \) time for unit points and \(o \left( n\varepsilon ^{-2}\,\mathrm{{log}}\,n \right) \) time for weighted points.