Anzeige
Erschienen in:
01.02.2013
Some variations on constrained minimum enclosing circle problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2013
EinloggenAktivieren 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
Abstract
Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows:
(i)
Computing k identical circles of minimum radius with centers on L, whose union covers all the points in P.
(ii)
Computing the minimum radius circle centered on L that can enclose at least k points of P.
(iii)
If each point in P is associated with one of the k given colors, then compute a minimum radius circle with center on L such that at least one point of each color lies inside it.
We propose three algorithms for Problem (i). The first one runs in O(nklogn) time and O(n) space. The second one is efficient where k≪n; it runs in O(nlogn+nk+k
2log3
n) time and O(nlogn) space. The third one is based on parametric search and it runs in O(nlogn+klog4
n) time. For Problem (ii), the time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. For Problem (iii), our proposed algorithm runs in O(nlogn) time and O(n) space.