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.