Back to Search
Start Over
Some Variations on Constrained Minimum Enclosing Circle Problem.
- Source :
- Combinatorial Optimization & Applications: 4th International Conference, Cocoa 2010, Kailua-kona, Hi, Usa, December 18-20, 2010, Proceedings, Part I; 2010, p354-368, 15p
- Publication Year :
- 2010
-
Abstract
- 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(nklogn) time and O(n) space. The second one runs in O(nk + k<superscript>2</superscript>log<superscript>3</superscript>n) time and O(nlogn) 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(nlogn + klog<superscript>4</superscript>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(nlogn) time algorithm for this problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642174575
- Database :
- Complementary Index
- Journal :
- Combinatorial Optimization & Applications: 4th International Conference, Cocoa 2010, Kailua-kona, Hi, Usa, December 18-20, 2010, Proceedings, Part I
- Publication Type :
- Book
- Accession number :
- 76855231
- Full Text :
- https://doi.org/10.1007/978-3-642-17458-2_29