Loading article…
数学と地理情報科学において、最短経路グラフは、ユークリッド平面上の点の集合から定義される無向グラフである。最短経路グラフは、点集合間の辺を推定し、推定された辺を通る最短経路が、点集合によって表される不正確な領域を通る最短経路とほぼ一致するというアイデアで提案されている。最短経路グラフの辺集合は、単一のパラメータt ≥ 1 に基づいて変化する。辺の重みが、そのユークリッド長さのパラメータt ≥ 1 乗として定義される場合 、その辺が最短経路グラフに存在するのは、その端点間の最小重み経路である場合のみである。[1]
最短経路グラフの特性
構成パラメータtが無限大になると、最短経路グラフは点集合の最小全域木になる。このグラフは点集合のガブリエルグラフのサブグラフであり、したがってそのデローネ三角形分割のサブグラフでもある。[1]
参考文献
- ^ ab de Berg, Mark ; Meulemans, Wouter; Speckmann, Bettina (2011). 「最短経路グラフによる不正確な領域の描写」。第 19 回 ACM SIGSPATIAL 国際地理情報システムの進歩に関する会議議事録 - GIS '11。第 19 巻。pp. 271–280。doi : 10.1145 / 2093973.2094010。ISBN 9781450310314. S2CID 2359926 . 2019年9月2日閲覧。