Max-Min Four-Dispersion Problems
摘要
Given a set P of n points on which facilities can be placed and an integer k,we want to place k facilities on k points in P so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 4-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the solution of the 2-dispersion problem corresponds to the diameter of P. We give an \(O(n^3)\) time algorithm to solve the 4-dispersion problem in the \(L_{\infty }\) metric, and an \(O(n^3)\) time algorithm to solve the 4-dispersion problem in the \(L_1\) metric. Also, we give an \(O(n^3\log ^2 n)\) time algorithm to solve the 4-dispersion problem in the \(L_2\) metric. Also, we give faster (but complicated) \(O(n^2\log n)\) -time algorithms to solve the max-min 4-dispersion problem for \(L_{\infty }\) metric and the \(L_1\) metric.