文献

J-GLOBAL ID：202102269587575136   整理番号：21A2703165

凸点集合のための線形サイズ平面Manhattanネットワーク【JST・京大機械翻訳】

Linear-size planar Manhattan network for convex point sets

著者 (3件)： Jana Satyabrata (Indian Statistical Institute, Kolkata, India) ,  Maheshwari Anil (School of Computer Science, Carleton University, Ottawa, Canada) ,  Roy Sasanka (Indian Statistical Institute, Kolkata, India)
資料名： Computational Geometry: Theory and Applications  (Computational Geometry: Theory and Applications)
巻： 100  ページ： Null  発行年： 2022年 
JST資料番号： W0536A  ISSN： 0925-7721  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： G=(V,E)はエッジ加重幾何グラフ(必ずしも平面ではない)であり,あらゆるエッジは水平または垂直である。エッジuv∈Eの重みは,そのエンドポイント間のL1距離である。WG(u,v)は,Gにおける頂点uとvの対の間の最短経路の長さを示す。グラフGは,もし,もし,P→Pに加えて,グラフGは頂点集合VにおけるSteiner点のセットTも含む。Manhattanネットワーク問題において,目的は一組のn点のために小サイズ(Steiner点の数)のManhattanネットワークを構築することである。この問題は,最初にGudmundsson et al.[EuroCG 2007]によって考察された。それらは,平面における一般的点集合のためのサイズΘ(nlogn)のManhattanネットワークの構築を与える。平面埋込みがあるならば,Manhattanネットワークは平面である。本論文では,O(n)Steiner点を用いて線形時間で凸点集合に対する平面Manhattanネットワークを構築した。また,凸点集合に対しても,Gudmundsson et al.[EuroCG 2007]における構築はΩ(nlog n)Steiner点を必要とし,ネットワークは平面ではないことを示した。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *ネットワーク ,  平面グラフ ,  線形性 ,  凸形
準シソーラス用語： *点集合 ,  エンドポイント ,  最短経路 , 【Automatic Indexing@JST】

著者キーワード (5件)： 凸点集合 ,  Manhattanネットワーク ,  ヒストグラム ,  平面グラフ ,  Steiner点

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

タイトルに関連する用語 (4件)： 凸 ,  点集合 ,  線形 ,  サイズ