Manhattan Distance Memo

published: 2020/9/13 update: 2020/9/13

Table of Contents

TL;DR

メモ。詳しくは最近の 45 度回転事情を参照してほしい。

マンハッタン距離

ある二点のマンハッタン距離は以下のように表される。

マンハッタン距離の最大値

点がm個与えられたとき、その点間のマンハッタン距離の最大値を求めたい。 もし全探索すると、かかってしまう。

そこで、45度回転させるという手法を使う。45度回転というのはとなる変換のこと。本来はが大きさとしてかかるが、大きさが本質でない場合は無視できる。つまり、などが見えたら45度回転の可能性を疑うとよい...らしい。

マンハッタン距離はそのままだと見えてこないが、以下のような変換を行うことでが現れる。

まず、絶対値を以下のように考える。

こうすると、マンハッタン距離は

こうすると、1番目と4番目、2番目と3番目に注目すると、そこは絶対値に戻すことができて

と表すことができるので、が出てくるので、と置くことができるようになってくる。

なので

と表すことができる。

もともとの目的は下の式が求めたいことであった。

これを変形すると

になって、最初のと二回目のは入れ替えても結果が変わらない。

になる。このとき、はそれぞれ独立に計算できるので、一番大きいものから一番小さいものを引けばいい。なので、

と書くことができて、側も同様にすると

こうするとのそれぞれの最大、最小を求めることはなので、解くことができる。

ちなみに高次元空間に拡大するとのとき、らしい。むずかしいね。

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

ofuse

Site Map

Table of Contents

  - TL;DR

  - マンハッタン距離

  - マンハッタン距離の最大値


当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

ofuse
Privacy Policy

Copyright © illumination-k 2021.