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

質問

上限のグラフと下限の折れ線グラフがあり、その上限と下限の中を通る直線の式（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.12

nag0720

今暇なので、最後に凹点の除外方法について。

凹点凸点の判定を、
「端点は凸点、端点以外は両隣りを結ぶ直線より下なら凹点、上なら凸点」
として、
左端から開始し、右端に達するまで下記の手順を実行する。
凸点なら、次の点（右隣り）を調べる。
凹点なら、その点を除外し、１つ前の点（左隣り）を調べる。

こうすれば、点の数がn個のとき最大でも2n回の判定で終了するのでオーダーｎで問題ないですね。

お礼

過去の凸点を保持しておくだけで可能なので、簡単で良いロジックですね。

即決で採用させていただきます(笑)

度々ありがとうございます。助かります。

回答No.11

nag0720

ひとつ思い違いをしていました。

凹点を除く計算をオーダーｎと書きましたが、これはグラフの状態によってはオーダーｎではできませんね。
点の両隣りから見れば凸点の場合でも、遠く離れた２点から見れば凹点になることがありますから、単純なアルゴリズムでは最悪の場合はｎの２乗のオーダーになるかもしれません。

これも何らかの工夫が必要でしょう。

まあ、平均で考えればそんなに気にする必要がないかもしれませんが。

お礼

確かにこの部分はちょっと引っかかりましたが深くは考えませんでした。

x=1から順に両隣をチェックしながら凹を除外した凸を作成・保持しつつ、局所的な凸が複数現れたら、随時マージするくらいに考えていました。

しかし大分できること出来ないことが分かってきて助かりました。

回答No.10

nag0720

＞でもこれはオーダーｎでいけますか？

確かに、中を通るかどうかの判定も含めればオーダーｎではありません。
ただそれを言うなら、もともとのオーダーはｎの２乗ではなくｎの３乗ですね。
中を通るかどうかの判定も含めてnのオーダーにする、というのは無理ではないかと思います。

＞単純に、X=1,2の下限同士を結んだ線の傾きと上限同士の線の傾きを比較して、下限の傾きの方が大き＞ければ右側で上限を超える・・・と言えますか？

言えません。
しかし、上限同士の線の傾きは昇順になっていますから、下限同士を結んだ線の傾きと比較して、大小が反転する箇所多くとも１箇所あります。
その１箇所だけ線の下にあるかどうかを判定すればいいことになります。

＃９の図で言うと、
上限の点を、左から順にa,b,c,d,e,fとします。
点A,Bを結ぶ直線の傾きより小さいのはab,bc,cd,deの線、大きいのはefの線。
よって、点eがABの線より上なら中を通る、下なら中を通らない、と判定できます。

直線ABと下限の線の傾きとを比較して点eを求める方法は、工夫すればLOG(n)のオーダーでできますから、全体のオーダーは、n*LOG(n)になります。

お礼

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

「単純に・・・」と言ったのはオーダーｎの方法だと思ったからでした。
他の部分がオーダーｎのようだったので。

しかし、n*log(n)ですか！
これはもはや、ほぼｎのオーダーと言っていいですね。

もう暫くしてから質問を締め切りたいと思います。

度々の回答ありがとうございました。

回答No.9

nag0720

＞「枠外」とはどんなことでしょうか？

単にグラフの中を通っているかどうかという意味です。グラフの上限を超えていたり、下限より下なら「枠外」です。

＞> 下限の左側の直線から調べていったとして、
＞から4行分が分かりません。

添付図で説明します。
点A,Bを通る直線は、Bの右側で上限を超えています。
点B,Cを通る直線は、Cの右側で上限を超えています。
点C,Dを通る直線は、Cの左側で上限を超えています。
点D,Eを通る直線は、Dの左側で上限を超えています。
点E,Fを通る直線は、Fの左側で上限を超えています。
よって、点Cが境界点になります。
あとは、点Cと上限の点を結んだ直線を調べます。

お礼

質問してしまって済みません。
分かりました。

でもこれはオーダーｎでいけますか？
#5の時とは状況が違うので、点A,Bを通る直線が右側で超えるのか左側で超えるのかは、線ABに対して上限の直線全部(凸で残ったもの)についてチェックしなければならなくないですか？

単純に、X=1,2の下限同士を結んだ線の傾きと上限同士の線の傾きを比較して、下限の傾きの方が大きければ右側で上限を超える・・・と言えますか？

だいぶ頭がこんがらがってきました(笑)

回答No.7

naniwacchi

#6です。

「凹になる」の判定ですが、
(両隣の点の平均)と(その点)との大小関係で判定することができます。

「上限」の点であれば、(両隣の点の平均)＜(その点)ならば除外
同様に、「下限」の点であれば、(両隣の点の平均)＞(その点)ならば除外
とすることはできます。

当然、各点の横軸の間隔が等しいことが条件です。

ざっくりとは、こんな感じかなあ。と。

・傾きゼロが言えるかどうかを判定する。

・傾きゼロがダメであれば、とりあえず考えられる直線の傾きを求める。
（その前に、上の方法である程度点を除外しておくか）
・その傾きの小さい順にソートをして
・その小さい順にすべての点との上下関係が満たされていることを確認する。

ソートしておいて一番最初に見つかったところで終了。という考えです。

お礼

凹判定ありがとうございます。

念のため補足ですが、#8さんが最後におっしゃっているように、基本的に全ての点が対象になりますね。
例えば#6の図でBmとBeの間の点の下限がBmよりもちょっぴり高かったときにそうなります。

この問題は二つの凸曲線の接線を求める感じに近いんですかね。
式で表せるようなものであればもっと簡単だったかもですが・・・。

回答No.6

naniwacchi

#4です。
「微妙なところ」の話ですね。

図を描いてみました。こういう感じですよね？
こうなると、Bmからすべての上限の点に線を引いて、
その傾きが一番小さくなるものを求めておく必要があるのかなあ？と思いました。
（実際には傾きだけを計算して、ソートしておく）

同様に、Umからもすべての下限の点に線を引くことになります。

お礼

ハイそうです。
図までありがとうございます。

出来れば、上限と下限の点を結んだ線について全部チェックするようなことはせずに、
X=1で何か計算をして、次にその結果とX=2の上限下限を考慮して何か計算をして、次にその結果とX=3の上限下限を考慮して・・・くらいの計算量で何とかならないかと考えていたのですが良い方法が思いつきませんでした。

計算量を削るアイデアを頂きましたのでもう少し考えてみます。

回答No.5

nag0720

＞傾き０の直線も全ての点で調べないといけないような気がします。

間違えました。
最大・最小の傾きではなくて、非負の最小、非正の最大の傾きです。
これならたぶん大丈夫でしょう。

それはともかく、ｎのオーダー位にしたいとなるとかなり難しいでしょう。

できるだけ計算量を少なくしたいということであれば、

まず、凹んでいる点は無視できます。（図の下限のx=2、上限のx=3）
また、上限の２点でできる直線も除くことができます。（もしそれが中を通るならそのまま下げていけば下限の点にぶつかるから）
下限の２点でできる直線は凹点を除いた隣り合った点でできる直線だけなので、n-1本以下。
中を通るかどうかは、上限の点（凹点は除く）だけを調べればいい。

問題は下限と上限の１点ずつでできる直線です。
下限の点をA、上限の点をB、直線ABの傾きをr、
Aの左側と右側の傾きをs1,s2、Bの左側と右側の傾きをt1,t2（これらも凹点を除いた隣点との傾き）とすると、
直線ABが中を通るかどうかは、rとs1,s2,t1,t2の大小関係だけで決まります。
（Bの横軸の値のほうが大きいとすると、s2≦r≦s1　, t1≦r≦t2　のとき中を通る）

ｎのオーダーにはほど遠いけど、これだけでも計算量はかなり減るでしょう。

お礼

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

なるほど、点の両側の傾きを使うわけですか。
点を結んだ直線ばかり見ていました。

詳細な説明ありがとうございます。
検討させていただきます。

回答No.4

naniwacchi

#2です。

＞図でいうとx=1の上限が35の時とか？
その場合、Us＝ Um＝ 35となるだけでは・・・？
端の点と最大・最小の点が一致する場合もあるということです。

・傾き＝ 0については、Um≧ Bmであれば得られますね。

お礼

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

例えばx=2.5に上限45くらいの点がある場合（つまりギリギリ青い実線に引っかかる場合）、
Umはx=2で変わらずですが、x=2は通らずに、x=2.5とx=3を通ると思います。

図が追加できれば分かりやすいんですがすみません。

回答No.3

nag0720

＞つまり必ず２点は通らないのです。

失礼、傾きの絶対値が最も小さい直線となると２点を通らない場合がありますね。

まあそれでも、

２点を通る直線のうち、条件を満たす直線の傾きが最大・最小となる直線を求める。
０≦最小≦最大　なら最小となる直線
最小≦最大≦０　なら最大となる直線
最小≦０≦最大　なら傾き０の直線
（傾き０の直線は、最大・最小の直線の２点計４点で、それぞれの点を通る傾き０の直線を調べる）

とすればいいのでは。

お礼

傾き０の直線も全ての点で調べないといけないような気がします。

例えば載せた図で上限が1000一定だった場合、傾き最大はx=1の下限とx=4の上限、傾き最小はx=1の上限とx=4の下限となりますから、x=3の下限の点１点のみを通る傾き０の直線が導けません。

回答を参考にもう少し考えてみます。
計算量を点数ｎの２乗ではなく、ｎのオーダー位にしたいんですよね。
無理なのかも知れませんが、感覚的に無理かどうかも分からない状況でして悩んでいます。

回答No.2

naniwacchi

こんにちわ。
質問の図をヒントにして考えてみました。

ポイントなるのは、以下の 6点かと。
Us)「上限」の左端となる点
Um)「上限」の最小値となる点
Ue)「上限」の右端となる点

Bs)「下限」の左端となる点
Bm)「下限」の最大値となる点
Be)「下限」の右端となる点

※Uは Upper、Bは Bottom、sは start、eは end、mは max/minの意です。

そして、「上」から1点、「下」からも1点を選んだ計 9とおりの直線が候補になると思います。
質問の図においては、直線Um－Bmという選択になります。

あとは、直線が「下限≦ y≦ 上限」という領域内にあることが条件となるので、
それを判定する必要があります。
これも直線の式を y＝ f(x)＝ ax+ bとすれば
　(x=1の下限)≦ f(1)≦ (x=1の上限)
　(x=2の下限)≦ f(2)≦ (x=2の上限)
　・・・
　(x=kの下限)≦ f(k)≦ (x=kの上限)
　・・・

がすべて満たされることを調べればよいと思います。

手順としては、
1) 9とおりの直線を求め、
2) 傾きの絶対値が小さい順にソートする。
3) 上の「下限≦ y≦ 上限」の判定をおこない、
4) 最初にクリアしたものが答え。
5) クリアしたものがなければ、解なし。

こんな感じでいかがかと。
すいません、漏れているところがあるかもしれません。

お礼

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

No.1の方へのお返事にも書いたのですが、１点しか通らない可能性があります。
また上限の最小値と下限の最大値を含めた６点では、最も小さい傾きの直線にはならないのです。

図でいうとx=1の下限が35の時とか？
ちょっと図を載せられなくて申し訳ないのですが、両端・上限の最小・下限の最大以外の点を通る可能性があります。

しかし皆さんのアドバイスを頂くと色々と見えてきてありがたいです。

なるべく計算やチェック回数が少ない方法を考えていたのですが、
１点を通る場合＋２点を通る場合の全てをチェックするしか無いような気もしてきました。
（ちょっと処理が煩雑になるので避けたいところですが）

もう少し回答の募集を継続したいと思います。

補足

ごめんなさい、お礼に対する補足なのですが、下限が35でなく上限が35でした。