JISE Vol.22 No.6 #1

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(n² log² n) expected-time algorithm for this problem, improving substantially the previous O(n⁵)- 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.