文献

J-GLOBAL ID：201802255514952215   整理番号：18A0616738

最小サイズの凸集合を用いた点被覆【Powered by NICT】

Covering points with convex sets of minimum size

著者 (5件)： Bae Sang Won (Kyonggi University, Suwon, Republic of Korea) ,  Cho Hwan-Gue (Pusan National University, Busan, Republic of Korea) ,  Evans William (University of British Columbia, Vancouver, Canada) ,  Saeedi Noushin (University of British Columbia, Vancouver, Canada) ,  Shin Chan-Su (Hankuk University of Foreign Studies, Yongin, Republic of Korea)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 718  ページ： 14-23  発行年： 2018年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 平面におけるn点の集合Pに対して,凸集合の全面積または周辺はO(n~4log n)とO(n~2log n)時間で最小化され,それぞれであることをこのようなPをカバーする二有界凸集合を見つけるためのアルゴリズムを提案した。前者は最小総面積のための最初の結果であり,後者は最小全周辺の最速の従来のアルゴリズム,O(n3)時間で走るの改善である。もO(n~2K(k 1)logn)時間で面積を最小にするk≧2凸集合を見出すためにこのアルゴリズムを拡張した。アルゴリズムは自動地図生成または部分的クラスタリングのための移動車両のGPS軌跡から道路交差点の検出に適用することができた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： クラスタ化 ,  *凸集合 ,  交差点 ,  被覆 ,  アルゴリズム ,  軌跡 ,  GPS
準シソーラス用語： GPS【位置決め】 ,  有界 , 【Automatic Indexing@JST】

著者キーワード (6件)： 被覆点 ,  凸集合 ,  凸包 ,  面積 ,  周辺 ,  計算幾何学

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 最小サイズ ,  凸集合