The search functionality is under construction.

The search functionality is under construction.

Given a set of *n* disjoint intervals on a line and an integer *k*, we want to find *k* points in the intervals so that the minimum pairwise distance of the *k* points is maximized. Intuitively, given a set of *n* disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer *k*, which is the number of times we will check something, we plan *k* checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the *k* checking times. We call the problem the *k*-dispersion problem on intervals. If we need to choose exactly one point in each interval, so *k*=*n*, and the disjoint intervals are given in the sorted order on the line, then two *O*(*n*) time algorithms to solve the problem are known. In this paper we give the first *O*(*n*) time algorithm to solve the problem for any constant *k*. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in *O*(log *n*) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the *k*-dispersion problem on disks, including an FPTAS.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1181-1186

- Publication Date
- 2022/09/01

- Publicized
- 2022/03/08

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2021DMP0004

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Algorithms and Data Structures

Tetsuya ARAKI

Gunma University

Hiroyuki MIYATA

Gunma University

Shin-ichi NAKANO

Gunma 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.

Copy

Tetsuya ARAKI, Hiroyuki MIYATA, Shin-ichi NAKANO, "Dispersion on Intervals" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1181-1186, September 2022, doi: 10.1587/transfun.2021DMP0004.

Abstract: Given a set of *n* disjoint intervals on a line and an integer *k*, we want to find *k* points in the intervals so that the minimum pairwise distance of the *k* points is maximized. Intuitively, given a set of *n* disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer *k*, which is the number of times we will check something, we plan *k* checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the *k* checking times. We call the problem the *k*-dispersion problem on intervals. If we need to choose exactly one point in each interval, so *k*=*n*, and the disjoint intervals are given in the sorted order on the line, then two *O*(*n*) time algorithms to solve the problem are known. In this paper we give the first *O*(*n*) time algorithm to solve the problem for any constant *k*. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in *O*(log *n*) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the *k*-dispersion problem on disks, including an FPTAS.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0004/_p

Copy

@ARTICLE{e105-a_9_1181,

author={Tetsuya ARAKI, Hiroyuki MIYATA, Shin-ichi NAKANO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Dispersion on Intervals},

year={2022},

volume={E105-A},

number={9},

pages={1181-1186},

abstract={Given a set of *n* disjoint intervals on a line and an integer *k*, we want to find *k* points in the intervals so that the minimum pairwise distance of the *k* points is maximized. Intuitively, given a set of *n* disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer *k*, which is the number of times we will check something, we plan *k* checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the *k* checking times. We call the problem the *k*-dispersion problem on intervals. If we need to choose exactly one point in each interval, so *k*=*n*, and the disjoint intervals are given in the sorted order on the line, then two *O*(*n*) time algorithms to solve the problem are known. In this paper we give the first *O*(*n*) time algorithm to solve the problem for any constant *k*. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in *O*(log *n*) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the *k*-dispersion problem on disks, including an FPTAS.},

keywords={},

doi={10.1587/transfun.2021DMP0004},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Dispersion on Intervals

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1181

EP - 1186

AU - Tetsuya ARAKI

AU - Hiroyuki MIYATA

AU - Shin-ichi NAKANO

PY - 2022

DO - 10.1587/transfun.2021DMP0004

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E105-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2022

AB - Given a set of *n* disjoint intervals on a line and an integer *k*, we want to find *k* points in the intervals so that the minimum pairwise distance of the *k* points is maximized. Intuitively, given a set of *n* disjoint time intervals on a timeline, each of which is a time span we are allowed to check something, and an integer *k*, which is the number of times we will check something, we plan *k* checking times so that the checks occur at equal time intervals as much as possible, that is, we want to maximize the minimum time interval between the *k* checking times. We call the problem the *k*-dispersion problem on intervals. If we need to choose exactly one point in each interval, so *k*=*n*, and the disjoint intervals are given in the sorted order on the line, then two *O*(*n*) time algorithms to solve the problem are known. In this paper we give the first *O*(*n*) time algorithm to solve the problem for any constant *k*. Our algorithm works even if the disjoint intervals are given in any (not sorted) order. If the disjoint intervals are given in the sorted order on the line, then, by slightly modifying the algorithm, one can solve the problem in *O*(log *n*) time. This is the first sublinear time algorithm to solve the problem. Also we show some results on the *k*-dispersion problem on disks, including an FPTAS.

ER -