Max-Min 3-dispersion on a Convex Polygon

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: Max-Min 3-dispersion on a Convex Polygon
• タイトル / 言語: en
• タイトル: Max-Min 3-dispersion on a Convex Polygon
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kyoto University
• 著者所属: Gunma University
• 著者所属: Yamagata University
• 著者所属: National Institute of Informatics
• 著者所属: Kyushu University
• 著者所属: Iwate University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者所属(英): en
• 著者所属(英): Yamagata University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Iwate University
• 著者名: Yasuaki, Kobayashi; Shin-ichi, Nakano; Kei, Uchizawa; Takeaki, Uno; Yutaro, Yamaguchi; Katsuhisa, Yamanaka
• 著者名(英): Yasuaki, Kobayashi; Shin-ichi, Nakano; Kei, Uchizawa; Takeaki, Uno; Yutaro, Yamaguchi; Katsuhisa, Yamanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 7, p. 1-4, 発行日 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
• 出版者: 情報処理学会