Max-Min 3-Dispersion Problems

Autor:	Takeaki Uno, Akira Suzuki, Toshiki Saitoh, Takashi Horiyama, Koki Suetsugu, Shin-ichi Nakano, Ryuhei Uehara, Kunihiro Wasa
Rok vydání:	2021
Předmět:	Plane (geometry) Applied Mathematics Minimum distance Binary logarithm Computer Graphics and Computer-Aided Design Facility location problem Set (abstract data type) Combinatorics Integer Signal Processing Metric (mathematics) Statistical dispersion Electrical and Electronic Engineering Mathematics
Zdroj:	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. :1101-1107
ISSN:	1745-1337 0916-8508
DOI:	10.1587/transfun.2020dmp0003
Popis:	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. 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_{\infty }\) metric, and an O(n) time algorithm to solve the 3-dispersion problem in the \(L_1\) metric. Also we give an \(O(n^2\log n)\) time algorithm to solve the 3-dispersion problem in the \(L_2\) metric.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0297d7fcb76fe477ab661dd17dbd85b6 https://doi.org/10.1587/transfun.2020dmp0003 Zobrazit plný text záznamu