پیوندهای مفید
آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 399 |
| تعداد مقالات | 5,389 |
| تعداد مشاهده مقاله | 5,288,013 |
| تعداد دریافت فایل اصل مقاله | 4,882,758 |
(n,1,1,α)-Center Problem | ||
| AUT Journal of Modeling and Simulation | ||
| مقاله 6، دوره 46، شماره 1، شهریور 2014، صفحه 57-64 اصل مقاله (584.49 K) | ||
| نوع مقاله: Research Article | ||
| شناسه دیجیتال (DOI): 10.22060/miscj.2014.535 | ||
| نویسندگان | ||
| P. Kavand1؛ A. Mohades* 2؛ M. Eskandari3 | ||
| 1PhD. Student of Computer Science, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran. | ||
| 2Associate Professor, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran | ||
| 3Assistant Professor, Department of Mathematics, Alzahra University, Tehran, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| computational geometry؛ K-Center Problem؛ Farthest Point Voronoi Diagram؛ Center Hull | ||
| عنوان مقاله [English] | ||
| (n,1,1,α)-Center Problem | ||
| نویسندگان [English] | ||
| P. Kavand1؛ A. Mohades2؛ M. Eskandari3 | ||
| 1PhD. Student of Computer Science, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran. | ||
| 2Associate Professor, Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran | ||
| 3Assistant Professor, Department of Mathematics, Alzahra University, Tehran, Iran | ||
| چکیده [English] | ||
| 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. | ||
| کلیدواژه‌ها [English] | ||
| computational geometry, K-Center Problem, Farthest Point Voronoi Diagram, Center Hull | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 1,052 تعداد دریافت فایل اصل مقاله: 1,337 |
||