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 nis the number of points in the plane.