凸位置の点集合におけるMax-Min3分散を計算するためのO(n<sup>2</sup>)時間アルゴリズム

KOBAYASHI Yasuaki; NAKANO Shin-ichi; UCHIZAWA Kei; UNO Takeaki; YAMAGUCHI Yutaro; YAMANAKA Katsuhisa

文献

J-GLOBAL ID：202202286804071318 整理番号：22A1077278

凸位置の点集合におけるMax-Min3分散を計算するためのO(n²)時間アルゴリズム

An O(n²)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=22A1077278&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=22A1077278&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (6件)： , , , , ,
資料名：
巻： E105.D 号： 3 ページ： 503-507(J-STAGE) 発行年： 2022年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

n個の点と整数kの集合Pを与えられたとき,施設間の最小距離が最大になるように,Pの点上にk個の施設を配置したい。この問題はk分散問題と呼ばれ,このようなk個の点の集合はPのk分散と呼ばれる。2分散問題はPの直径の計算に対応することを意味する。したがって,k分散問題は直径問題の自然な一般化である。本論文では,Pが凸位置にあるときの3分散問題であるk=3の場合を考察した。O(n²)時間アルゴリズムを提示し,Pの3分散を計算した。(翻訳著者抄録)

, , , ,
,

著者キーワード (2件)： ,

数値計算

引用文献 (27件)：

[1] P.K. Agarwal and M. Sharir, “Efficient algorithms for geometric optimization,” ACM Comput. Surv., vol.30, no.4, pp.412-458, 1998. 10.1145/299917.299918
[2] T. Akagi, T. Araki, T. Horiyama, S. Nakano, Y. Okamoto, Y. Otachi, T. Saitoh, R. Uehara, T. Uno, and K. Wasa, “Exact algorithms for the max-min dispersion problem,” Proc. FAW 2018, LNCS 10823, pp.263-272, 2018. 10.1007/978-3-319-78455-7_20
[3] T. Akagi and S. Nakano, Dispersion on the line, IPSJ SIG Technical Reports, 2016-AL-158-3, 2016.
[4] K. Amano and S. Nakano, “An approximation algorithm for the 2-dispersion problem,” IEICE Trans. Inf. & Syst., vol.E103-D, no.3, pp.506-508, 2020. 10.1587/transinf.2019fcp0005
[5] T. Araki and S. Nakano, “The max-min dispersion on a line,” Proc. COCOA 2018, LNCS 11346, pp.672-678, 2018. 10.1007/978-3-030-04651-4_45

, , , , ,

前のページに戻る

凸位置の点集合におけるMax-Min3分散を計算するためのO(n2)時間アルゴリズム

凸位置の点集合におけるMax-Min3分散を計算するためのO(n²)時間アルゴリズム