# Separated Red Blue Center Clustering

@article{Eskandari2021SeparatedRB, title={Separated Red Blue Center Clustering}, author={Marzieh Eskandari and Bhavika B. Khare and Nirman Kumar}, journal={ArXiv}, year={2021}, volume={abs/2107.07914} }

We study a generalization of k-center clustering, first introduced by Kavand et. al., where instead of one set of centers, we have two types of centers, p red and q blue, and where each red center is at least α distant from each blue center. The goal is to minimize the covering radius. We provide an approximation algorithm for this problem, and a polynomial time algorithm for the constrained problem, where all the centers must lie on a line `.

#### References

SHOWING 1-10 OF 17 REFERENCES

Clustering to Minimize the Maximum Intercluster Distance

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1985

An O(kn) approximation algorithm that guarantees solutions with an objective function value within two times the optimal solution value is presented and it is shown that this approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. Expand

The Aligned k-Center Problem

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 2011

In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line l such… Expand

Smallest enclosing circle centered on a query line segment

- Mathematics, Computer Science
- CCCG
- 2008

Given a set of n points P, it is shown how to preprocess P such that for any query line segment L the authors can report in O(logn) time the smallest enclosing circle whose center is constrained to lie on L . Expand

Exact and Approximation Algorithms for Clustering

- Mathematics, Computer Science
- SODA '98
- 1998

An n^ O(k1-1/d) -time algorithm for solving the k -center problem in \realsd , under L∈fty - and L2 -metrics and extends to other metrics, and to the discrete k - center problem. Expand

The slab dividing approach to solve the EuclideanP-Center problem

- Mathematics, Computer Science
- Algorithmica
- 2005

This paper presents an algorithm with time complexityO(n0(√P)), the most efficient algorithm for finding P supply points on the plane. Expand

Constrained Facility Location

- 2000

In this paper we consider constrained versions of the minimax facility location problem. We provide an O(n + m) time algorithm for the problem of constructing the minimum enclosing circle of a set of… Expand

On the Complexity of Some Common Geometric Location Problems

- Mathematics, Computer Science
- SIAM J. Comput.
- 1984

The p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard and the reductions are from 3-satisfiability. Expand

Efficient Algorithm for Placing Base Stations by Avoiding Forbidden Zone

- Computer Science
- ICDCIT
- 2005

This work considers the forbidden region P as convex and base station can be placed on the boundary of the region and presents optimum linear time algorithms for these problems. Expand

Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications

- Mathematics, Computer Science
- Proceedings of CG International '96
- 1996

This paper addresses the problem of computing locations that possess several geometric characteristics of the pin gate, and shows how to compute the geodesic centre of M, when it is constrained to lie in a polygonal region, in O[n(n+k)] time. Expand

Variations of Base-Station Placement Problem on the Boundary of a Convex Region

- Computer Science, Mathematics
- Int. J. Found. Comput. Sci.
- 2007

The objective is to position the base stations such that each point in the entire area can communicate with at least one base-station, and total power required for all the base-stations in the network is minimized. Expand