高次元最小全域木

• 最小全域木
  • N個のノードがある
  • すべてのノードが連結であるようなグラフのうち、エッジの数が最少なとき、その数はN-1
  • ここで、エッジの重さ(長さ)の和が最小であるようなエッジの取り方があり、そのようなエッジのセットでノードを連結したとき、それを最小全域木という
  • これは、空間中にノードの位置を配慮して「１次元」的な枝分かれ構造を作成することである
• これを高次元に一般化しよう
  • N個のノードがある(同じ)
  • すべてのノードがグラフで言うところの連結であるとは、「少なくとも１つの『辺』の端」になっていること
    • ここで次元を上げる
    • 『辺』は「１次元」的なものなので、これを「高次元」的なものにする
    • 直線→平面→その高次元化したもの
  • すべてのノードがk次元的に連結であるとは、「少なくとも１つの『k次元的直線/平面』の端になっていること
  • これを「高次元エッジ」と呼ぶことにする
  • ここで「高次元エッジ」の「『長さ』に相当するもの」の和が最小であるような「高次元エッジ」の取り方があり(あることを確認する必要がある)、そのような「高次元エッジのセットでノードを連結したとき、それを「高次元最小全域木」と呼ぶことにする
  • これは、空間中にノードの位置を配慮して「k次元」的な枝分かれ構造を作成することである
  • さて「高次元エッジ」の「『長さ』に相当するもの」は、長さ→面積→体積→、と置くと、すわりがよいだろう
• では、どれくらい高次元にこれが作成できるだろうか？
• ノードがn次元空間にあるときに、k=n-1まではできそうだ
• それより大きいkにすると、一意に決まらなくなりそう(k<=n-1でも一意に決まるかどうかの確認をしていないけれど)だが、それはそれとして置いて置いて、定義できるとすると、「ワープ」とか「抜け道」とかのある、ゆがんだ空間にも展開ができそうで、ユークリッドで考える範囲と、ユークリッドを仮定しない範囲とで、定義を変えることも有意義かもしれない