Some variations on constrained minimum enclosing circle problem

Arindam Karmakar, Sandip Das (), Subhas C. Nandy and Binay K. Bhattacharya
Additional contact information
Arindam Karmakar: Tezpur University
Sandip Das: ACM Unit
Subhas C. Nandy: ACM Unit
Binay K. Bhattacharya: Simon Fraser University

Journal of Combinatorial Optimization, 2013, vol. 25, issue 2, No 2, 176-190

Abstract: 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.

Keywords: Computational geometry; Minimum enclosing circle; Parametric searching; Voronoi diagram (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9452-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:25:y:2013:i:2:d:10.1007_s10878-012-9452-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9452-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().