Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Some Variations on Constrained Minimum Enclosing Circle Problem
verfasst von : Arindam Karmakar, Sandip Das, Subhas C. Nandy, Binay K. Bhattacharya
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
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
Given a set
P
of
n
points and a straight line
L
, we study three important variations of minimum enclosing circle problem. The first problem is on computing
k
circles of minimum (common) radius with centers on
L
which can cover the members in
P
. We propose three algorithms for this problem. The first one runs in
O
(
nk
log
n
) time and
O
(
n
) space. The second one runs in
O
(
nk
+
k
2
log
3
n
) time and
O
(
n
log
n
) space assuming that the points are sorted along
L
, and is efficient where
k
< <
n
. The third one is based on parametric search and it runs in
O
(
n
log
n
+
k
log
4
n
) time. The next one is on computing the minimum radius circle centered on
L
that can enclose at least
k
points. The time and space complexities of the proposed algorithm are
O
(
nk
) and
O
(
n
) respectively. Finally, we study the situation where the points are associated with
k
colors, and the objective is to find a minimum radius circle with center on
L
such that at least one point of each color lies inside it. We propose an
O
(
n
log
n
) time algorithm for this problem.