複数の範囲を通る直線の求め方について

質問

上限のグラフと下限の折れ線グラフがあり、その上限と下限の中を通る直線の式（y=ax+b）を求めたいと思っています。
プログラムを作って機械的に解きたい（Java）ので解法を考えていたのですが、なかなか良い方法が思い浮かびません。

・X=1,2,3,4に対して、それぞれ上限の点と下限の点があります。上限のみ、下限のみということはありません。
・図では横軸が1～4の4点の例ですが、3点以上で可変にしたいです。
・直線は上限、下限と接しても問題ありません。
・グラフによっては、中を通る直線が存在しない場合もありますので、その場合は解法の途中で「無理」であることを認識したいです。
・グラフによっては、中を通る直線の可能性が沢山あると思いますが、その場合は傾きの絶対値が最も小さい直線を求めたいです。（図で言うと、青い点線よりも青い実線の式を求めたい。）

解き方や解き方のアイデアがある方がいましたら教えてください。
条件は書いたつもりですが、不明点や曖昧な点がありましたら指摘頂ければ追記させていただきます。
宜しくお願いします。

回答No.8

nag0720 · ベストアンサー

ｎのオーダーで計算する方法です。

まず、凹点を除きます。
残りの点だけでグラフを作ると、凸グラフになります。（正確には、下限は上に凸、上限は下に凸）
この２つの凸グラフが重なっていれば中を通る直線は存在しません。
重なっていなければ中を通る直線は必ず存在します。

重なっているかどうかの判定まではｎのオーダーで計算できます。

以下は、凹点を除いた凸グラフで、２つの凸グラフが重なっていないとします。

下限の凸グラフの点がk個だとすると、グラフの直線はk-1本。
まず、そのk-1本が中を通るかどうかを判定します。

中を通る直線が存在した場合は、そのうちの絶対値が最小の傾きの直線を求めます。
で、その直線を定めた２点の大きい方の点と、上限の点を結んだ直線のうち、中を通るもので傾きの絶対値が最小の直線が求める直線となります。
ただし、下限の点が下限の最大値の場合は、傾き０の直線についても中を通るかどうか判定します。

ここまでもｎのオーダーで計算できます。

下限の凸グラフのk-1本の直線が全て中を通らない場合は、
下限の左側の直線から調べていったとして、
はじめのうちは、２点の右側で枠外になっていて、ある時点から２点の左側で枠外になり、それ以降はずっと左側で枠外になります。
つまり、枠外になるのが右側から左側に変わる境界点がただ１つ存在します。（左右両方とも枠外になることはない）
で、その境界点と上限の点を結んだ直線のうち、中を通るもので傾きの絶対値が最小の直線が求める直線となります。
これも、境界点が下限の最大値の場合は、傾き０の直線についても中を通るかどうか判定します。

これもｎのオーダーで計算できますから、全体でもｎのオーダーで計算できるはずです。

ただし、直線が中を通るかどうかの判定方法にも＃５で書いたような工夫が必要だと思います。

あと、計算量をできるだけ少なくしたいなら、調べる直線の順番を傾きの絶対値が小さい順にすることでしょうか。

#7さんへ
端短,Um,Bmどれも通らない直線が求める直線になる場合もありますから、結局は全ての２点を通る直線が候補になります。

お礼

これ本当にｎのオーダーで出来んの？と思ったら各ステップ毎に検査範囲が狭められていて恐れ入ります。
アルゴリズムレベルまで落としていただいて申し訳ありません。

で、済みませんが説明がよく分からない部分がありまして、「枠外」とはどんなことでしょうか？

> 下限の左側の直線から調べていったとして、

から4行分が分かりません。
下限の左側の直線というのは下限のx=1とx=2の直線のことですか？

回答No.1

nag0720

X=1,2,・・・,n　とすると、点の数は2n個

中を通る直線があるとすれば、それは2n個のうちの２個の点を通るとしてよい。

なので、高々n(2n-1)本の直線を調べればいいのでは。

お礼

回答ありがとうございます！

回答頂いて気づいたのですが、複数の線が存在したときの切片の条件がありませんでした。
切片の条件は最も小さいものとしたいと思います。

それで例えば載せた図で上限が80一定だった場合、x=3の下限の点１点のみを通る傾き０の直線になると思います。
つまり必ず２点は通らないのです。

回答を参考にもう少し考えてみます。

補足

複数の線が存在したときの切片の条件がありませんでした。
切片の条件は最も小さいものとしたいと思います。