IEICE TRANSACTIONS on Fundamentals
Open Access
Max-Min 3-Dispersion Problems
-
Full Text Views
35
- Cite this
- Free PDF (1.5MB)
Summary :
Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1101-1107
- Publication Date
- 2021/09/01
- Publicized
- 2021/03/19
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2020DMP0003
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures
Authors
Takashi HORIYAMA
Hokkaido University
Shin-ichi NAKANO
Gunma University
Toshiki SAITOH
Kyushu Institute of Technology
Koki SUETSUGU
National Institute of Informatics
Akira SUZUKI
Tohoku University
Ryuhei UEHARA
JAIST
Takeaki UNO
National Institute of Informatics
Kunihiro WASA
Toyohashi University of Technology
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
Takashi HORIYAMA, Shin-ichi NAKANO, Toshiki SAITOH, Koki SUETSUGU, Akira SUZUKI, Ryuhei UEHARA, Takeaki UNO, Kunihiro WASA, "Max-Min 3-Dispersion Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1101-1107, September 2021, doi: 10.1587/transfun.2020DMP0003.
Abstract: Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0003/_p
Copy
@ARTICLE{e104-a_9_1101,
author={Takashi HORIYAMA, Shin-ichi NAKANO, Toshiki SAITOH, Koki SUETSUGU, Akira SUZUKI, Ryuhei UEHARA, Takeaki UNO, Kunihiro WASA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Max-Min 3-Dispersion Problems},
year={2021},
volume={E104-A},
number={9},
pages={1101-1107},
abstract={Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.},
keywords={},
doi={10.1587/transfun.2020DMP0003},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Max-Min 3-Dispersion Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1101
EP - 1107
AU - Takashi HORIYAMA
AU - Shin-ichi NAKANO
AU - Toshiki SAITOH
AU - Koki SUETSUGU
AU - Akira SUZUKI
AU - Ryuhei UEHARA
AU - Takeaki UNO
AU - Kunihiro WASA
PY - 2021
DO - 10.1587/transfun.2020DMP0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2021
AB - Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.
ER -
English
