Diameter partitioning |
| |
Authors: | David Avis |
| |
Institution: | (1) School of Computer Science, McGill University, 805 Sherbrooke St. W., H3A 2K6 Montreal, Canada |
| |
Abstract: | We discuss the problem of partitioning a set of points into two subsets with certain conditions on the diameters of the subsets and on their cardinalities. For example, we give anO(n
2 logn) algorithm to find the smallestt such that the set can be split into two equal cardinality subsets each of which has diameter at mostt. We also give an algorithm that takes two pairs of points (x, y) and (s, t) and decides whether the set can be partitioned into two subsets with the respective pairs of points as diameters. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|