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

A Different Approach for Solving the

Specified Diameter Partition Problem

**Chiou-Kuo Liang, Chuan-Yi Tang ^{*}and R. C. T. Lee^{*}**

Chung Hua Polytechnic Institute

Hsinchu, Taiwan 300, R.O.C.

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(*n*log*n*) 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.