IEICE TRANSACTIONS on Information
An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.503-507
- Publication Date
- 2022/03/01
- Publicized
- 2021/11/01
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021FCP0013
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
- Category
Authors
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
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
