| Previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
¡@
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.
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.