(n,1,1,α)-Center Problem

Document Type : Research Article

Authors

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.

Keywords

References

[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.

Files

Share

How to cite

Statistics