The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
세트가 주어지면 P of n 포인트와 정수 k, 우리는 배치하고 싶습니다 k 포인트 시설 P 시설간 최소거리를 극대화하였습니다. 문제는 k- 분산 문제, 그리고 그러한 세트 k 포인트라고 불리는 k-의 분산 P. 2-분산 문제는 다음의 직경 계산에 해당합니다. P. 그래서 k- 분산 문제는 직경 문제의 자연스러운 일반화입니다. 본 논문에서는 다음의 경우를 고려한다. k=3, 이는 3-분산 문제입니다. P 볼록한 위치에 있습니다. 우리는 O(n2)-시간 알고리즘으로 3-분산을 계산합니다. P.
Yasuaki KOBAYASHI
Kyoto University
Shin-ichi NAKANO
Gunma University
Kei UCHIZAWA
Yamagata University
Takeaki UNO
National Institute of Informatics
Yutaro YAMAGUCHI
Osaka University
Katsuhisa YAMANAKA
Iwate University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yasuaki KOBAYASHI, Shin-ichi NAKANO, Kei UCHIZAWA, Takeaki UNO, Yutaro YAMAGUCHI, Katsuhisa YAMANAKA, "An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 503-507, March 2022, doi: 10.1587/transinf.2021FCP0013.
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(n2)-time algorithm to compute a 3-dispersion of P.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0013/_p
부
@ARTICLE{e105-d_3_503,
author={Yasuaki KOBAYASHI, Shin-ichi NAKANO, Kei UCHIZAWA, Takeaki UNO, Yutaro YAMAGUCHI, Katsuhisa YAMANAKA, },
journal={IEICE TRANSACTIONS on Information},
title={An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position},
year={2022},
volume={E105-D},
number={3},
pages={503-507},
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(n2)-time algorithm to compute a 3-dispersion of P.},
keywords={},
doi={10.1587/transinf.2021FCP0013},
ISSN={1745-1361},
month={March},}
부
TY - JOUR
TI - An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position
T2 - IEICE TRANSACTIONS on Information
SP - 503
EP - 507
AU - Yasuaki KOBAYASHI
AU - Shin-ichi NAKANO
AU - Kei UCHIZAWA
AU - Takeaki UNO
AU - Yutaro YAMAGUCHI
AU - Katsuhisa YAMANAKA
PY - 2022
DO - 10.1587/transinf.2021FCP0013
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - 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(n2)-time algorithm to compute a 3-dispersion of P.
ER -