TY - GEN
T1 - Bichromatic 2-center of pairs of points
AU - Arkin, Esther M.
AU - Díaz-Báñez, José Miguel
AU - Hurtado, Ferran
AU - Kumar, Piyush
AU - Mitchell, Joseph S.B.
AU - Palop, Belén
AU - Pérez-Lantero, Pablo
AU - Saumell, Maria
AU - Silveira, Rodrigo I.
PY - 2012
Y1 - 2012
N2 - We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points, assign to each point a color ("red" or "blue") so that each pair's points are assigned different colors and a function of the radii of the minimum enclosing balls of the red points and the blue points, respectively, is optimized. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii. For each case, minmax and minsum, we consider distances measured in the L 2 and in the L ∞ metrics. Our problems are motivated by a facility location problem in transportation system design, in which we are given origin/destination pairs of points for desired travel, and our goal is to locate an optimal road/flight segment in order to minimize the travel to/from the endpoints of the segment.
AB - We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points, assign to each point a color ("red" or "blue") so that each pair's points are assigned different colors and a function of the radii of the minimum enclosing balls of the red points and the blue points, respectively, is optimized. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii. For each case, minmax and minsum, we consider distances measured in the L 2 and in the L ∞ metrics. Our problems are motivated by a facility location problem in transportation system design, in which we are given origin/destination pairs of points for desired travel, and our goal is to locate an optimal road/flight segment in order to minimize the travel to/from the endpoints of the segment.
UR - https://www.scopus.com/pages/publications/84860814510
U2 - 10.1007/978-3-642-29344-3_3
DO - 10.1007/978-3-642-29344-3_3
M3 - Conference contribution
AN - SCOPUS:84860814510
SN - 9783642293436
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 36
BT - LATIN 2012
T2 - 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
Y2 - 16 April 2012 through 20 April 2012
ER -