Name
Title | ||
|---|---|---|
An O(n(2))-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position |
Abstract | ||
|---|---|---|
Given a set P of n points and an integer k, we wish to place k facilities on points in P so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem, and the set of such k points is called a k-dispersion of P. Note that the 2-dispersion problem corresponds to the computation of the diameter of P. Thus, the k-dispersion problem is a natural generalization of the diameter problem. In this paper, we consider the case of k = 3, which is the 3-dispersion problem, when P is in convex position. We present an O(n(2))-time algorithm to compute a 3-dispersion of P. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1587/transinf.2021FCP0013 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | DocType | Volume |
dispersion problem, facility location | Journal | E105D |
Issue | ISSN | Citations |
3 | 1745-1361 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yasuaki Kobayashi | 1 | 0 | 0.68 |
| Shin-ichi Nakano | 2 | 246 | 24.40 |
| Kei Uchizawa | 3 | 0 | 0.34 |
| Takeaki Uno | 4 | 1319 | 107.99 |
| Yutaro Yamaguchi | 5 | 0 | 0.34 |
| Katsuhisa Yamanaka | 6 | 0 | 0.68 |