インテジャーズ

INTEGERS

数、特に整数に関する記事。

線分の交点と七角形定理

私が大学生のときに個別指導の塾で指導していた生徒が次のような問題を考えてきました。

問題設定 多角形の二頂点を結んで出来る全ての線分を考え、その線分の交点を取る。その後、多角形の頂点および得られた交点の中から二点を結んで出来る全ての線分を考え、その線分の交点を取る。この操作を続けていくとき、途中で停止せず交点が無限に増えていくのはどのような場合か?

ここで、多角形は単純多角形のみを考え、凸多角形に限らず凹多角形も扱うものとします。

まず、三角形、四角形の場合は停止します。図は凸四角形と凹四角形の例で、赤線・緑点は追加された線分・頂点を表します。

f:id:integers:20180215225457p:plain:w400
f:id:integers:20180215224935p:plain:w400

n \geq 5に対して、凸n角形の場合は無限に交点が増えます。

証明. 凸五角形の場合に示せば十分。

f:id:integers:20180215225953p:plain:w400

図のように、操作を行うと凸五角形の内部に小さな凸五角形が現れるため、操作を無限に続けられることがわかる。 Q.E.D.

一方、凹五角形と凹六角形には停止する例があります。

f:id:integers:20180215230800p:plain:w400
f:id:integers:20180215232032p:plain:w400

そうして、生徒は次のような予想を立てました。

生徒の予想 n \geq 7であれば、n角形に対して操作は無限に続けられるであろう。

たくさん図を描いてみた結果どうやらこの予想は正しそうに思えるけれど、まわりの生徒や教師は解けなかったので先生解いてくれませんか?という感じに言われ、この問題を解くことにしました。

はじめに問題設定を少し変えました:

\mathbb{R}^2内の有限個の点からなる集合Pに対して、T(P)Pの二点を結んで出来る線分同士の交点*1として得られる点をPに追加した集合と定義し、\displaystyle P_{\infty} := \bigcup_{n=0}^{\infty}T^n(P)とする。

\#P_{\infty} < \inftyであるときP有限配置であるといい、\#P_{\infty} = \inftyであるときP無限配置であるという。

Q \subset PのときT(Q) \subset T(P)が成り立つことに注意。特に、Qが無限配置であればPも無限配置である(これによって主定理の証明中、一部分のみに注目することが許される)。

定義1 平行でない二直線l_1, l_2の交点Al_1Aで二分したときに同じ側にある二点、l_2Aで二分したときに同じ側にある二点の計五点で構成される集合のことをV5配置という。

f:id:integers:20180216005347p:plain:w400

定義2 直線l上の有限個の点と\mathbb{R}^2におけるlの補集合の二つの連結成分のそれぞれに高々一つの点を含むような有限点集合のことを\div配置という。

f:id:integers:20180216005526p:plain:w400

「高々一つ」の点は文字通りなくてもよいです。つまり、一直線上に配置された有限点集合も\div配置です。また、凹五角形と凹六角形の停止例も\div配置であることがわかります。

この設定のもと、次の定理が成り立つことがわかりました。

主定理 有限点集合Pが有限配置であるための必要十分条件はP\div配置であるか、図
f:id:integers:20180216010554p:plain:w400
のような六点からなる配置(三角形の中に三角形があり、小さな三角形の二頂点と大きな三角形の一つの頂点が同一直線上にあるような配置)であることである。

その後調べたところ、この定理は1997年には既にEppsteinによって"Dilation-Free Planar Graphs"として知られていました。

補題 V5配置は無限配置である。

証明. V5配置に三回Tを施すと、

f:id:integers:20180216011714p:plain:w400

図のように例えばA, B, C, D, Eが新しいV5配置となっている。凸包である三角形が小さくなっているため、Tを施す操作を繰り返せば無限に交点が得られることがわかる。 Q.E.D.

ハッピーエンド問題の証明法にヒントを得た場合分けをし、各場合に補題を適用することによって主定理が証明されます*2

主定理の証明. 十分性は明らかであるため、必要性を示す。有限点集合P\div配置でも主張にある六点配置でもないと仮定する。このとき、Pが無限配置であることを示せばよい。Pが有限点集合であることから、その凸包は多角形である。以下、場合分けを行って、全ての場合に有限回Tを施すとV5配置が生じることをみる(実際には高々二回でよい)。すると、補題によってPが無限配置であることが従う。

凸包がn角形(n \geq 5)の場合: 凸包が定めるn角形の頂点は最初に見たとおり無限配置である(内部に五角形が生じる形で証明したが、V5配置も生じている)。

凸包が四角形の場合: 更に場合分けを行う。

凸包が定める四角形の辺と対角線によって生じる四つの小三角形のいずれかの内部にPの点が一つでもある場合:

f:id:integers:20180216014848p:plain:w400 f:id:integers:20180216014901p:plain:w400

V5配置あり。

凸包が定める四角形の辺上に頂点と異なるPの点が一つでもある場合: 上と同様にV5配置が生じる(内部の点を辺上まで移動させた図を想像せよ)。

上記二つの場合以外にあり得るのはPの点が凸包が定める四角形の四頂点以外は全て四角形の対角線上に乗っている場合であるが、P\div配置ではないと仮定しているため、対角線のそれぞれに対角線の交点とは異なるPの点が少なくとも一つずつ乗っていなくてはならない。

上記の場合:

f:id:integers:20180216024308p:plain:w400

V5配置あり。

凸包が三角形の場合: 凸包が定める三角形の頂点以外のPの点が全て三角形の辺上にある場合は、P\div配置でないため、二つの辺上に少なくとも一つずつ以上Pの点が乗っていなくはならない。このとき、明らかにV5配置を含む。よって、以下、三角形の内部にPの点が少なくとも一つある場合を考え、そのような点を一つ固定する。その点と三角形の頂点を結んで出来る三つの直線を補助線として考える。

f:id:integers:20180216025500p:plain:w400

P\div配置ではないため、少なくとももう一点なくてはならない。

その「もう一点」が補助線である三直線上にない場合:

f:id:integers:20180216030738p:plain:w400

V5配置あり。

図は「もう一点」が内部にある場合を描いているが、凸包が定める三角形の辺上にあっても同様である(ただし、補助線である三直線上との交点ではない)。

「もう一点」が補助線である三直線上にある場合:

f:id:integers:20180216031925p:plain:w400

このままではP\div配置となってしまうため、更に少なくとももう一点Pの点が存在する(固定する)。それはPの三点が乗っているピンクの補助線および下図の黒点ではないと仮定してよい(もし黒点しか取れなければ、主張にある六点配置となってしまう。また、上の図において「(二つ目の)もう一点」が凸包の定める三角形の辺上にあってもよく、その場合は単に黒点が存在しない)。

f:id:integers:20180216032317p:plain:w400

なお、

f:id:integers:20180216041031p:plain:w400

のような配置の場合は「一つ目のもう一点」と「二つ目のもう一点」を入れ替えると同じ状況になるため省略してよい。

「二つ目のもう一点」が三角形ABC内にある場合(ただし、辺上はAC上(頂点A, Cは除く)のみ許す):

f:id:integers:20180216033641p:plain:w400

V5配置あり。

「二つ目のもう一点」が三角形ABD内にある場合(ただし、辺上はAD上(頂点A, Dは除く)のみ許す):

f:id:integers:20180216034727p:plain:w400

V5配置あり。

「二つ目のもう一点」が線分AE上にある場合(ただし、A, Eは除く)。

f:id:integers:20180216040401p:plain:w400

V5配置あり。

「二つ目のもう一点」が線分BE上にある場合(ただし、B, Eは除く)。

f:id:integers:20180216035512p:plain:w400

V5配置あり。

「二つ目のもう一点」がPの三点が乗っているピンクの補助線の反対側にある場合も同様なので、全ての場合にV5配置が生じることが示された。 Q.E.D.

有限点集合Pが無限配置であるための必要十分条件は、T^2(P)V5配置をなす五点を含むことである。

証明. 主定理の証明よりわかる。 Q.E.D.

七角形定理 生徒の予想は正しい。

証明. 主定理によって、単純七角形の頂点をなす七点が\div配置になり得ないことを示せばよい。そこで、単純七角形の頂点をなす七点が\div配置をなすと仮定する。このとき、或る直線lが存在して、l上に少なくとも五点存在する。単純多角形の各頂点には丁度二本の辺が接続されていることに注意する。lの外にある点(高々二点)とl上の点を結ぶ辺は高々四本なので、l上の五点のうち少なくとも一点はその点と接続する二本の辺がl上になければならないことがわかる。するとその点は七角形の頂点とは認められない(内角180^{\circ}となってしまう)。 Q.E.D.

私が調べたのは以上ですが、Pが無限配置である場合にP_{\infty}がどのような配置となるかについて気になります。実はこれについて

A. Grüne, S. Kamali, On the density of iterated line segment intersections, Comput. Geom. Vol. 40, Issue 1, (2008), 23−36.

で非常に美しい定理が証明されていることを知ったため、最後にその結果を紹介してこの記事を締めくくりたいと思います。

定義&命題 有限点集合Pに対して、K(P)
\displaystyle K(P) := \bigcap_{a \in P}\bigcap_{H \supset P\setminus \{a\}}H
と定義する。ここで、HP\setminus \{a\}を含む閉半平面とする。このとき、K(P)P_{\infty}\setminus Pを含むような凸多角形であり、K(P)の頂点集合はT(P)に含まれる。

Pが凸五角形の頂点からなる場合はK(P)は内部にできる凸五角形です。

f:id:integers:20180216050838p:plain:w400

次の定理は決定的と言えるでしょう。

稠密性定理 (Grüne-Kamali) 有限点集合Pが無限配置であると仮定する。このとき、P_{\infty}K(P)内で稠密に分布する。


ミスを指摘してくださったじゃいろさんに感謝致します。

*1:線分の交点とは、二つの線分の共通部分が一点となるときのその一点のことをいうこととする。例えば、二点A, Bの中点をCとするとき、線分ABと線分ACは共通部分をもつが、交点は存在しないと解釈する。

*2:証明中の図において、頂点の色付けの微妙なミス(同じ色だと思っていたら違った)がありますがご容赦願います。