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^{++}
**

Tamkang University

Taipei, 251 Taiwan

E-mail: h0138@ms7.hinet.net

Providence University

Taichung, 433 Taiwan

E-mail: yttsai@pu.edu.tw

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*(*n*^{2} log^{2} *n*)
expected-time algorithm for this problem, improving substantially the previous *O*(*n*^{5})-
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

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.