Kavand, P., Mohades, A., Eskandari, M. (2014). (n,1,1,α)-Center Problem. AUT Journal of Modeling and Simulation, 46(1), 57-64. doi: 10.22060/miscj.2014.535

P. Kavand; A. Mohades; M. Eskandari. "(n,1,1,α)-Center Problem". AUT Journal of Modeling and Simulation, 46, 1, 2014, 57-64. doi: 10.22060/miscj.2014.535

Kavand, P., Mohades, A., Eskandari, M. (2014). '(n,1,1,α)-Center Problem', AUT Journal of Modeling and Simulation, 46(1), pp. 57-64. doi: 10.22060/miscj.2014.535

Kavand, P., Mohades, A., Eskandari, M. (n,1,1,α)-Center Problem. AUT Journal of Modeling and Simulation, 2014; 46(1): 57-64. doi: 10.22060/miscj.2014.535

^{1}PhD. Student of Computer Science, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.

^{2}Associate Professor, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

^{3}Assistant Professor, Department of Mathematics, Alzahra University, Tehran, Iran

Abstract

Given a set of points in the plane and a constant ,-center problem is to find two closed disks which each covers the whole , the diameter of the bigger one is minimized, and the distance of the two centers is at least . Constrained -center problem is the -center problem in which the centers are forced to lie on a given line . In this paper, we first introduce -center problem and its constrained version. Then, we present an algorithm for solving the -center problem. Finally, we propose a linear time algorithm for its constrained version.

[1] Rezaei, M., and FazelZarandi, M.H., “Facility location via fuzzy modeling and simulation,” Applied soft computing, Vol. 11, pp. 5330– 5340, 2011. [2] Megiddo, N., and Supowit, K., “On the complexity of some common geometric location problems,” SIAM J. Comput., Vol. 13, pp. 1182– 1196, 1984. [3] Agarwal, P. K., and Procopiuc, C. M., “Exact and approximation algorithms for clustering,” Algorithmica, Vol. 33, pp. 201.226, 2002. [4] Sylvester, J. J., “A question in the geometry of situation,” Quart. J. Math., pp. 79, 1857. [5] Megiddo, N., “Linear time algorithms for linear programming in ℝ3,” Society for Industrial and Applied Mathematics, Vol. 12, No. 4. November 1983. [6] Drezner, Z., “The planar two-center and two-median problems,” Transportation Science, Vol. 18, pp. 351- 361, 1984. [7] Hershberger, J., and Suri, S., “Finding tailored partitions,” J. Algorithms, Vol.12, pp. 431– 463, 1991. [8] Agarwal, P. K., and Sharir, M., “Planar geometric location problems,” Algorithmica, Vol.11, pp. 185– 195, 1994. [9] Megiddo, N., “Applying parallel computation algorithms in the design of serial algorithms,” J. ACM, Vol.30, pp. 852– 865, 1983. [10] Eppstein, D., “Dynamic three-dimensional linear programming,” ORSA J. Computing, Vol.4, pp. 360– 368, 1992. [11] Jaromczyk, J., and Kowaluk, M., “An efficient algorithm for the euclidean two-center problem,” Proc. 10th ACM Sympos. Comput. Geom, pp. 303– 311, 1994. [12] Sharir, M., “A near linear algorithm for the planar 2-center problem,” Discrete Comput. Geom., Vol.18, pp. 125– 134, 1997. [13] Eppstein, D., “Faster construction of planar two-centers,” Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pp. 131– 138, 1997. [14] Chan, T. M., “More planar two-center algorithms,” Comput. Geom. Theory Appl., Vol.13, pp. 189– 198, 1999. [15] Huang, P. H., Tsai, Y. T., and Tang, C. Y., “A near-quadratic algorithm for the alpha-connected two-center problem,” Journal Of Information Science and Engineering, Vol. 22, pp. 1317- 1324, 2006. [16] Huang, P. H., Tsai, Y. T., and Tang, C. Y., “A fast algorithm for the alpha-connected two-center decision problem,” Information Processing Letters, Vol. 85, pp. 205- 210, 2003. [17] Rao, A. S., Goldberg, K., “Manipulating algebraic parts in the plane,” Technical Report RUU-CS-93-43, 1993. [18] Preparata, F. P., and Shamos, M. I., “Computational Geometry: An Introduction,” Springer Verlag, New York, 1985.