k-Dispersion on Intervals

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: k-Dispersion on Intervals
• タイトル / 言語: en
• タイトル: k-Dispersion on Intervals
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Gunma University
• 著者所属: Gunma University
• 著者所属: Gunma University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者名: Tetsuya, Araki; Hiroyuki, Miyata; Shin-ichi, Nakano
• 著者名(英): Tetsuya, Araki; Hiroyuki, Miyata; Shin-ichi, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 the 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. The problem is called 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. Here one can check twice or more in one time interval. 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 a PTAS.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 the 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. The problem is called 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. Here one can check twice or more in one time interval. 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 a PTAS.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 2, p. 1-5, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会