ask.fmに来た、凸n角形を作れる点集合についての問題を解いた

久しぶりにask.fmの字数制限にひっかかったので。ろくにチェックしてないけどもう投げる。問題は

「平面上にn>3個の点があるとする。それを結んで凸n角形を作ることができるための必要十分条件は、"そのn個の点からどのように3つの点を選んでもその3つの点を結んでできる3角形の内部(境界含む)に他の点が入らないこと"である」を証明または反証してください。

曲がりなりにも数学者にただで問題を解けとはふてえやろうだと思いつつ、門前払いするのも逃げたような気がするので考えてしまった。

まず、必要条件であることは簡単で、三角形ABCの内部にDがあると、どんなふうに凸n角形を作ろうがA, B, Cが頂点にある限りDはその内部に入ってしまうので凸n角形の頂点にならない。

というわけで十分条件になることを証明する。わりと図を描くと明らかなんだよね。凸n角形があったとき、もう一点Eをとってくると、その凸n角形上の連続した点A, B, C, Dで、Fを直線ABと直線CDの交点としたときに、Eが三角形BCFの内部に入るようなものが存在する。ここで、EをBとCの間に入れてやると凸(n+1)角形が作れる。
でも、図を描いて証明とするのが、図に騙されそうで嫌なのと、基本的にスマホで書いているのでお絵かきしにくいという事情で、代数的な証明を書くぞと思ったらとんでもなく時間がかかってしまった。

多分、ほとんど車輪の再発明なんだろうなぁ。もうこれ誰も読まないだろうけど、一応置いとく。「vの(特定の)法線とwの内積」とかの記号を準備して、projectionとか使っていったほうがはるかに簡単に書けた気がする。

A, B∈R^2に対して、v(A, B)でAからBへのベクトルを表すことにする。

とりあえず、全ての点が一直線に並んでいるケースは除外。その端の点から端の点までの線分はある意味凸n角形にも見えるけど、すごく特殊だ。

A, B, C, D∈R^2に対して、A, B, Cが同一線上にないとき、実数r1(D, A, B, C)とr2(D, A, B, C)をv(A, D)=r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)となるようなものとしてとる。要するにv(A, D)を基底{v(A, B), v(A, C)}について表現したもの。r2(D, A, B, C)=r1(D, A, C, B)なんだけど、気分がでないので両方定義しておく。

(補題1)R^2の有限部分集合Xが"そのn個の点からどのように3つの点を選んでもその3つの点を結んでできる3角形の内部(境界含む)に他の点が入らないこと"を満たすことと、任意のA, B, C, D∈Xに対して、
(i)r1(D, A, B, C)≠0かつr2(D, A, B, C)≠0
(ii)r1(D, A, B, C)<0ならば、r2(D, A, B, C)>0
が成り立つことは同値。

(証明) (⇒)まず、三点が一直線上にならばないことを証明する。A, B, C∈Xが一直線上にこの順番で並んでいたとする。このとき、この直線上にない一点D∈Xをとると、三角形ACD内にBがあるので条件に反する。

さて、任意のA, B, C, D∈Xをとって、b=r1(D, A, B, C), d=r2(D, A, B, C)とする。Xに属する三点が同一線上に並ばないことからb≠0かつc≠0。b<0を仮定し、c>0を導くためにc<0を仮定する。このとき、(-b)v(A, B)+(-c)v(A, C)+v(A, D)=0(ベクトル)か言える。よって、明らかにAは三角形BCDの内部にある。これは矛盾。

いや明らかにって書いたし絵を描くと明らかっぽく見えるけど、どうきっちり書けばよいのだろう。三角形は凸だから、三角形BCDの境界を含む内部はv(A, E)=b' v(A, B)+c' v(A, C)+d' v(A, D)かつb', c', d'>0かつb'+c'+d'=1をみたすようなE全体の集合になる。というわけで、Aが三角形BCDの境界を含む内部に属するためにはb' v(A, B)+c' v(A, C)+d' v(A, D)=0かつb', c', d'>0かつb'+c'+d'=1をみたすようなb', c', d'があればよい。のだけど、b'+c'+d'=1以外の条件はb', c', d'を同時に定数倍してもみたされ続けるので、b'+c'+d'=1をみたすように変更することは容易。ってことで、大丈夫かな。

(⇐)任意のA, B, C, D∈Xに対して、Dが三角形ABCの内部に属さないことを示す。背理法のため、Dが三角形ABCの内部に属していると仮定する。b=r1(D, A, B, C), d=r2(D, A, B, C)とする。このとき、条件によりb≠0かつc≠0。また、Dが三角形ABCの内部に属していることよりb>0かつc>0かつb+c≦1となる。
すると、v(A, C)=(-b/c) v(A, B)+(1/c) v(A, D)。ここで、v(D, A)=-v(A, D)かつv(A, B)=-v(D, A)+v(D, B)であることを使うと、v(A, C)=(-b/c) (-v(D, A)+v(D, B) )+(-1/c) v(D, A)=(-b/c) v(D, B)+( (b-1)/c) v(D, A)。すると、b+c≦1であることから、b-1≦-c<0。よって、(-b/c) <0かつ(b-1)/c<0。これは条件に矛盾する。
(補題証明了)

この条件を(*)とでも書こうか。

(補題2) 任意の点A, B, C, Dに対して、
(i) r1(D, B, A, C)=r1(D, C, A, B)=1-r1(D, A, B, C)-r2(D, A, B, C)、
(ii) r2(D, B, A, C)=r2(D, A, B, C)
(iii) r2(D, C, A, B)=r1(D, A, B, C)、
(証明)
v(B, D)=v(B, A)+v(A, D)=v(B, A)+r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)=v(B, A)-r1(D, A, B, C) v(B, A)+r2(D, A, B, C) (v(A, B)+v(B, C))=v(B, A)-r1(D, A, B, C) v(A, B)-r2(D, A, B, C) v(B, A)+r2(D, A, B, C) v(B, C)=(1-r1(D, A, B, C)-r2(D, A, B, C)) v(B, A)+r2(D, A, B, C) v(B, C)。よって, r1(D, B, A, C)=1-r1(D, A, B, C)-r2(D, A, B, C)かつr2(D, B, A, C)=r2(D, A, B, C)。

前段の結果を使うと、r1(D, C, A, B)=1-r1(D, A, C, C)-r2(D, A, B, C)
(証明了)

もう一つ補題
(補題3){A, B, C, D}が(*)をみたすとする。もし、r1(D, A, B, C)<0ならば、
(i) r2(D, A, B, C)<1-r1(D, A, B, C)
(ii) r1(D, C, A, B)>0かつr2(D, C, A, B)<0
(iii) r1(D, B, A, C)>0かつr2(D, B, A, C)>0。

(証明)
(i) 補題2により、r1(D, C, A, B)=1-r2(D, A, B, C)-r1(D, A, B, C)かつr2(D, C, A, B)=r1(D, A, B, C)。すると、r2(D, C, A, B)<0なので、r1(D, C, A, B)>0。補題2により、1-r2(D, A, B, C)-r1(D, A, B, C)=r1(D, C, A, B)。よって、1-r2(D, A, B, C)-r1(D, A, B, C)>0なので、r1(D, A, B, C)<1-r2(D, A, B, C)。

(ii) (i)の証明より。

(iii) v(B, D)=v(B, A)+v(A, D)=v(B, A)+r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)=(1-r1(D, A, B, C) ) v(B, A)+r2(D, A, B, C) (v(A, B)+v(B, C) )=(1-r1(D, A, B, C)-r2(D, A, B, C) ) v(B, A)+r2(D, A, B, C) v(B, C)。よって、(i)よりr1(D, B, A, C)=1-r1(D, A, B, C)-r2(D, A, B, C)>0 かつr2(D, B, A, C)=r2(D, A, B, C)>0。
(証明了)

(補題4)
A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してr1(A_k, A_i, A_{i-1}, A_{i+1})>0となることは同値。なお、Aの添字はmod nで考えてもらうことにして、例えばi=1のときは、r1(A_k, A_1, A_n, A_2)>0と解釈する。
(証明)
ここで、n(A_i, A_{i+1})を、A_i A_{i+1}の単位法線ベクトルで、v(A_i, A_{i-1})・n(A_i, A_{i+1})>0となるようなものとする。すると、A_iとA_{i+1}を通る直線を考えて平面をそれで2つの部分に分けたとき、任意のk≠i, i+1に対してA_{i-1}とA_kが同じ部分に入るということと、v(A_i, A_k)・n(A_i, A_{i+1})>0が同値になる。というわけで、まず、A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してv(A_i, A_k)・n(A_i, A_{i+1})>0が成り立つことが同値となる。

よって、任意のiとkに対して、v(A_i, A_k)・n(A_i, A_{i+1})とr1(A_k, A_i, A_{i-1}, A_{i+1})の符号が一致することをいえばよい。これは、v(A_i, A_k)・n(A_i, A_{i+1})=(r1(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i-1})+r2(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i+1}))・n(A_i, A_{i+1})=r1(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i-1})・n(A_i, A_{i+1})となるので、v(A_i, A_{i-1})・n(A_i, A_{i+1})>0となることからいえる。
(証明了)

(補題4')A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してr1(A_k, A_i, A_{i-1}, A_{i+1})>0かつr2(A_k, A_i, A_{i-1}, A_{i+1})>となることは同値。

ここまでくれば大丈夫。帰納法でやることにする。n≧3を自然数として、任意のR^2のn元部分集合Xに対して、(*)が成り立てばXの元を結んで凸n角形をつくることができることを仮定する。ここで、任意のR^2のn+1元部分集合Xに対して、(*)が成り立てばXの元を結んで凸(n+1)角形をつくることを示す。Xの元Dを任意に取り、X'=X\{D}とする。帰納法の仮定により、X'の元を結んだn凸角形A_1, …, A_nが存在する。

(補題5)r1(D, A_i, A_{i-1}, A_{i+1})<0となるようなiが一つだけ存在する。
(証明) さすがにめんどうになってきた。絵を描けばわかるでしょ。∠A_i A_1 A_2 < ∠D A_1 A_2 < A_{i+1} A_1 A_2となるようなiをとればよい。一意性もいいよね。
(証明了)

ここで、A_1, …, A_i, D, A_{i+1}, …, A_nが凸(n+1)角形となることを示す。
必要なら添字を振り直して、i=2を仮定してもよい。ここで、
(i) 任意のk≠1,2に対して、r1(A_k, A_2, A_1, D)>0
(ii) 任意のk≠3, 4に対して、r1(A_k, A_3, D, A_4)>0
(iii) 任意のk≠2, 3に対して、r1(A_k, D, A_2, A_3)>0
(iv) 任意のk≠2, 3に対してr1(D, A_k, A_{k-1}, A_k)>0
をいえばよい。b=r1(D, A_2, A_1, A_3), c=r2(D, A_2, A_1, A_3)とする。b<0かつc>0となることに注意。b'=r1(D, A_3, A_2, A_4), c'=r2(D, A_3, A_2, A_4)とする。

(Claim) b'>0かつc'<0
(証明)
v(A_3, D)=v(A_3, A_2)+v(A_2, D)=v(A_3, A_2)+b v(A_2, A_1)+c v(A_2, A_3)=(1-c) v(A_3, A_2)+b v(A_2, A_1)
=(1-c) v(A_3, A_2)+b (v(A_3, A_1)-v(A_3, A_2))=(1-c-b) v(A_3, A_2) +b (r1(A_1, A_3, A_2, A_4)v(A_3, A_2)+r2(A_1, A_3, A_2, A_4)v(A_3, A_4))=(1-c-b+b (r1(A_1, A_3, A_2, A_4)) v(A_3, A_2) +b r1(A_1, A_3, A_2, A_4) v(A_3, A_4)。よって、r2(D, A_3, A_2, A_4)=b r1(A_1, A_3, A_2, A_4)<0。よって、r1(D, A_3, A_2, A_4)>0。
(Claim証明了)

(i) 任意のkに対して、r1(A_k, A_2, A_1, D)>0

まず、v(A_2, D)=b v(A_2, A_1)+c v(A_2, A_3)なのでv(A_2, A_3)=(-b/c) v(A_2, A_1)+(1/c) v(A_2, D)。

よって、v(A_2, A_k)=r1(A_k, A_2, A_1, A_3) v(A_2, A_1)+r2(A_k, A_2, A_1, A_3) v(A_2, A_3)=r1(A_k, A_2, A_1, A_3) v(A_2, A_1)+r2(A_k, A_2, A_1, A_3) ( (-b/c) v(A_2, A_1)+(1/c) v(A_2, D) )=(r1(A_k, A_2, A_1, A_3)-r2(A_k, A_2, A_1, A_3) (b/c) ) v(A_2, A_1)+(r2(A_k, A_2, A_1, A_3)/c) v(A_2, D)。よって、r1(A_k, A_2, A_1, D)=r1(A_k, A_2, A_1, A_3)-r2(A_k, A_2, A_1, A_3) (b/c)>0。

(ii) 任意のkに対して、r1(A_k, A_3, D, A_4)>0

v(A_3, D)=b' v(A_3, A_2)+c' v(A_3, A_4)なので、
v(A_3, A_2)=(v(A_3, D)-c' v(A_3, A_4))/b'。よって、r1(A_2, A_3, D, A_4)>0かつr2(A_2, A_3, D, A_4)>0。
すると、v(A_3, A_k)=r1(A_k, A_3, A_2, A_4) v(A_3, A_2)+r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=r1(A_k, A_3, A_2, A_4) (r1(A_2, A_3, D, A_4) v(A_3, D)+r2(A_2, A_3, D, A_4) v(A_3, A_4))+r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=r1(A_k, A_3, A_2, A_4) r1(A_2, A_3, D, A_4) v(A_3, D)+(r1(A_k, A_3, A_2, A_4) r2(A_2, A_3, D, A_4)+r2(A_k, A_3, A_2, A_4))v(A_3, A_4)。これにより、r1(A_k, A_3, D, A_4)=r1(A_k, A_3, A_2, A_4) r1(A_2, A_3, D, A_4)>0。

(iii) 任意のkに対して、r1(A_k, D, A_2, A_3)>0

v(A_3, D)=b' v(A_3, A_2)+c' v(A_3, A_4)なので、v(A_3, A_4)=(1/c') v(A_3, D)-(b'/c') v(A_3, A_2)=(1/c') v(A_3, D)-(b'/c') (v(D, A_2)-v(D, A_3))=-(b'/c') v(D, A_2)+(-1/c'+b'/c') v(D, A_3)

v(D, A_k)=v(D, A_3)+r1(A_k, A_3, A_2, A_4) v(A_3, A_2) +r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=v(D, A_3)+r1(A_k, A_3, A_2, A_4) (v(D, A_2)-v(D, A_3))+r2(A_k, A_3, A_2, A_4) (-(b'/c') v(D, A_2)+(-1/c'+b'/c') v(D, A_3))=(r1(A_k, A_3, A_2, A_4)-r2(A_k, A_3, A_2, A_4) (b'/c'))v(D, A_2)+(1-r1(A_k, A_3, A_2, A_4)+r2(A_k, A_3, A_2, A_4) (-1/c'+b'/c') )v(D, A_3))。よって、r1(A_k, D, A_2, A_3)=(r1(A_k, A_3, A_2, A_4)-r2(A_k, A_3, A_2, A_4) (b'/c'))>0

(iv) 任意のkに対してr1(D, A_k, A_{k-1}, A_k)>0

補題5による。

      • -

興味があるのは、これはより高い次元に拡張できるのかってことだけど、えーと、誰か教えて。