Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.3, pp.337-357 (September 1993)
A Different Approach for Solving the
Specified Diameter Partition Problem

Chiou-Kuo Liang, Chuan-Yi Tang*and R. C. T. Lee*
 Department of Computer Science
Chung Hua Polytechnic Institute
Hsinchu, Taiwan 300, R.O.C.
*Institute of Computer Science
National Tsing Hua University
Hsinchu, Taiwan, R.O.C.

In this paper, we propose an algorithm for solving the specified diameter partition problem. The specified diameter partition problem becides whether a set of points in plane can be partitioned into two disjoint subsets such that the diameters of the two subsets are equal to the distances between two given pairs of points or not. The algorithm for the specified diameter partition problem exploits some geometric properties. Our approach is based upon maximum spanning trees. Then, by using some geometric properties, the problem can be solved in O(nlogn) time, where n is the number of points in the plane.

Keywords: algorithms, computational geometry, maximum spanning trees, specified diameter partition problem

Received December 1, 1991; revised May 15, 1993.
Communicated by Chin-Chen Chang.