Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Smallest Maximum-Weight Circle for Weighted Points in the Plane
verfasst von : Sergey Bereg, Ovidiu Daescu, Marko Zivanic, Timothy Rozario
Erschienen in: Computational Science and Its Applications -- ICCSA 2015
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
P
be a weighted set of points in the plane. In this paper we study the problem of computing a circle of smallest radius such that the total weight of the points covered by the circle is maximized. We present an algorithm with polynomial time depending on the number of points with positive and negative weight. We also consider a restricted version of the problem where the center of the circle should be on a given line and give an algorithm that runs in
$$O(n(m+n) \log (m+n))$$
time using
$$O(m+n)$$
space. The algorithm can report all
k
smallest maximal weight circles with an additional
O
(
k
) space. Moreover, for this version, if all positively weighted points are required to be included within the circle then we prove a number of interesting properties and provide an algorithm that runs in
$$O((n+m) \log (n+m))$$
time.