JISE

[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

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 (JISE_200606_01.pdf)