Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19]

¡@

Journal of Information Science and Engineering, Vol. 22 No. 6, pp. 1317-1324 (November 2006)

A Near-Quadratic Algorithm for the Alpha-Connected Two-Center Problem*

Po-Hsueh Huang, Yin-Te Tsai+ and Chuan-Yi Tang++
Department of Computer Science and Information Engineering
Tamkang University
Taipei, 251 Taiwan
E-mail: h0138@ms7.hinet.net
+Department of Computer Science and Communication Engineering
Providence University
Taichung, 433 Taiwan
E-mail: yttsai@pu.edu.tw
++Department of Computer Science
National Tsing Hua University
Hsinchu 300, Taiwan
E-mail: cytang@cs.nthu.edu.tw

Given a set S of n points in the plane and a constant £\, the alpha-connected twocenter problem is to find two congruent closed disks of the smallest radius covering S, such that the distance of the two centers is at most 2(1 - £\)r. We present an O(n2 log2 n) expected-time algorithm for this problem, improving substantially the previous O(n5)- time solution. The algorithm translates the alpha-connected two-center problem into a distance problem between two circular hulls.

Keywords: computational geometry, algorithm, p-center problem, alpha-connected twocenter problem, circular hull

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200611_01.pdf)

Received January 3, 2003; revised June 23, 2003 & May 27 & October 21, 2005 & January 19, 2006;
accepted May 22, 2006; communicated by Jeremy P. Spinrad.
* This work was partially supported by the National Science Council of Taiwan, R.O.C., under grant No. NSC 89-2213-E-126-005.