文献あり

【解説アニメ付き】点集合の要素数と直径数について

はじめに

　この記事では、平面における点集合の要素数、およびその直径の数の関係について紹介します。
　なお、解説動画(下記URL)があるので、そちらもご覧ください。
　 https://www.youtube.com/watch?v=ImKNtsWKkTU

内容

　2次元平面に3つ以上の点がある時、2点を結ぶ線分の集まりの中で最も長い線分を直径と呼ぶ事にします[1]。直径は複数存在する場合があります。直径の数が特定の値になる(要素数が有限の)点集合は無数に考えることができますが、もっとも要素数の少ない集合の、その値はいくつでしょうか？　ここでは、この問題に関係したいくつかの命題を、証明と共に並べます。
　まず、前提として次のような条件が満たされる状況を考えます。
　①2次元平面に、 $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ という $2 n$ 個の点がある。ただし、 $n$ は3以上の整数である。
　②線分 $p_{i} {p^{'}}_{i}$ (1 $\leq$ $i$ $\leq$ $n$ )は直径である。また、その他の全ての線分は直径より短い。
　③直径の本数を数える時、複数の直径について、それぞれの両端の座標がどちらも同一となる場合、それらをまとめて1本の直径とみなして求められた値を真の直径数と呼ぶ。 $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ の真の直径数は $n$ である。

　点集合に属する2点は、今後の操作によって、同一の座標に存在する可能性があります。③は、そのような状況において、「完全に重なっている2本の直径は1本の直径とみなす」ための条件です。
　ただし、今後の都合のため、はじめは $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ のそれぞれの座標が相異なっているとします。念のため、条件①②③を満たす点の配置の存在に触れると、円上に $n$ 個の点を置き、それぞれの対となる点を直径を成すように置く場合があります。

$p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ の中から3つの点を選ぶ時、その3点が同一直線上に並ぶことはない。

　3つの点を選ぶ時、ある直径の両端となる2点を含むパターンとそうでないパターンがある。どちらの場合も、3つの点が同一直線上にある事を仮定すると、それぞれの場合で矛盾が起こることを示す。

1.ある直径の両端となる2点を含むパターン
　選んだ2点の中にある $p_{i}$ , ${p^{'}}_{i}$ を結んでできる線分が直径であるとする。残りの1点 $p_{j}$ は線分 $p_{i} {p^{'}}_{i}$ の間に存在する。 $p_{j}$ と結んで直径となる点 ${p^{'}}_{j}$ を考える。この時、幾何的な考察から、線分 ${p^{'}}_{j} {p^{'}}_{i}$ と線分 ${p^{'}}_{j} {p^{'}}_{i}$ の少なくとも一方は、必ず線分 $p_{j} {p^{'}}_{j}$ より長くなっている。これは、線分 $p_{j} {p^{'}}_{j}$ が直径であることに矛盾する。

2.ある直径の両端となる2点を含まないパターン
　3点のうち、選んだ3点を通る直線上において、他の2つに挟まれる位置にある点 $p_{i}$ を考える。他の2点を $p_{j}$ , $p_{k}$ とおく。この時、幾何的な考察から、直径となる線分 $p_{i} {p^{'}}_{i}$ よりも、線分 $p_{i} p_{j}$ または線分 $p_{i} p_{k}$ のうち、少なくとも一方の方が長い。これは、線分 $p_{i} {p^{'}}_{i}$ が直径であることに矛盾する。

$p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ の中から任意の3つの点を選ぶ。この時、選ばなかった各点は全て、選んだ3点を結ぶ三角形の内部にはない。

　命題1より、 $p_{1}$ ,..., ${p^{'}}_{n}$ の中から任意の3つの点を選ぶと、それらを結んで必ず三角形ができることに注意する。 $p_{1}$ ,..., ${p^{'}}_{n}$ から、任意の1点 $p_{i}$ を選ぶ。次に、残りの点の中から、任意の3つの点を選ぶ。この時、次の2通りを考える。

1.任意に選んだ3つの点の中に ${p^{'}}_{i}$ がないパターン
　この3点で成す三角形の内部に $p_{i}$ が含まれると仮定する。この時、 $p_{i}$ を通り、かつ ${p^{'}}_{i}$ から $p_{i}$ への方向と直交する直線を考える。その直線によって、平面は2つの領域に分かれるが、このうち、 ${p^{'}}_{i}$ を含まない方の領域に注目すると、その領域の中には、任意に選んだ3つの点のうち、少なくとも1つが含まれている。そのような点と ${p^{'}}_{i}$ を結んでできる線分は、線分 $p_{i} {p^{'}}_{i}$ より長い。しかし、これは線分 $p_{i} {p^{'}}_{i}$ が直径になることと矛盾している。

2.任意に選んだ3つの点の中に ${p^{'}}_{i}$ があるパターン
　この3点で成す三角形の内部に $p_{i}$ が含まれると仮定する。この時、直径である線分 $p_{i} {p^{'}}_{i}$ が三角形の内部に含まれることになり、矛盾が起こる。

$p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ に対し、それらを頂点とする凸2𝑛角形を平面に考えることができる。

　まず、 $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ に対し、その中から3つの点 $p_{a}$ , $p_{b}$ , $p_{c}$ を選ぶ。命題1より、その3点を結ぶことで三角形を考えることができる。次に、残りの $2 n - 3$ 個の点の中から1つの点 $p_{i}$ を選ぶ。この時、 $p_{i}$ は命題2より、既に選んだ3点を結んでできる三角形の内部にはない。ここで、はじめに選ぶ3点を $p_{i}$ , $p_{b}$ , $p_{c}$ とし、後から選ぶ1点を $p_{a}$ と取り替えても、同じ議論ができる。はじめに選ぶ3点を $p_{a}$ , $p_{i}$ , $p_{c}$ 、3点を $p_{a}$ , $p_{b}$ , $p_{i}$ としても同様である。従って、 $p_{a}$ , $p_{b}$ , $p_{c}$ , $p_{i}$ を上手く結ぶと、「 $p_{a}$ , $p_{b}$ , $p_{c}$ , $p_{i}$ のうち、どの2点を選んでも、その線分が内部また境界に含まれる」四角形を考えることができ、これは凸四角形である。同様に、4つの点を選んだ後に任意の1点を選ぶと、それらを頂点とする凸五角形を考えることができる。この考え方の延長で、凸2𝑛角形を平面に考えることができる。

　以下、凸角形と呼ぶ図形は、 $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ を結んでできる凸角形とします。また、 $m$ 個の点が同一座標にある場合は、それらを1点と考え、凸 $(n - m)$ 角形とみなします。

$p_{i}$ , $p_{j}$ が凸多角形のある辺の両端にある時、 ${p^{'}}_{i}$ , ${p^{'}}_{j}$ も凸多角形のある辺の両端にある。

　まず、 $p_{1}$ , $p_{2}$ , ${p^{'}}_{1}$ , ${p^{'}}_{2}$ についての位置関係について考える。直線 $p_{1} {p^{'}}_{1}$ によって2分割される平面の領域を考えると、 $p_{2}$ と ${p^{'}}_{2}$ はそれぞれ異なる領域にある。もし同じ領域にある場合、線分 $p_{1} {p^{'}}_{1}$ の端点と線分 $p_{2} {p^{'}}_{2}$ の端点を結んでできる線分で、直径よりも長いものが存在してしまい、矛盾が起きるからである。次に、 $p_{3}$ , ${p^{'}}_{3}$ を考える。直線 $p_{1} {p^{'}}_{1}$ と直線 $p_{2} {p^{'}}_{2}$ によって4分割される平面の領域を考えると、先程と同じ理由で、 $p_{3}$ と ${p^{'}}_{3}$ はそれぞれ、対角の関係にある領域にある。この時、点の配置は命題4の主張に一致する。同様の考え方で、 $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ に対して、命題4の主張を導くことができる。

　以上の状況から、「凸多角形の1辺の両端の点を、条件②③を破ることなく動かし、座標を一致させる」ことを考えます。この操作をマージと呼ぶことにします。

座標が互いに異なる状態にある $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ という点の集まりについて、マージを繰り返すことを考える。この時、マージを $(n + 1)$ 回以上行うことはできない。

　マージ時には、単に2点を重ねるだけでなく、真の直径の数を保つ必要があることに注意します。

　 $p_{i}$ , $p_{j}$ に対してマージを1回行った後の凸多角形を考える。この時、線分 ${p^{'}}_{i} {p^{'}}_{j}$ は凸多角形の1辺であるが、マージされた1点を $p$ とおくと、三角形 ${p p^{'}}_{i} {p^{'}}_{j}$ は2本の直径を2辺として持つ三角形になる。従って、線分 ${p^{'}}_{i} {p^{'}}_{j}$ は、「その両端にマージを試みると、2本の直径が重なり合い、真の直径の数が1つ減ってしまい、結果としてマージできない」(☆)ような線分である。このように、マージを繰り返すと、その後にできる凸多角形上に(☆)の特徴を持つ辺の本数が1だけ増える。
　座標が互いに異なる $p_{1}$ , $p_{2}$ ,..., $p_{n}$ , ${p^{'}}_{1}$ ,..., ${p^{'}}_{n}$ という点の集まりに対し、マージを $n$ 回行った後、全ての辺が、(☆)の特徴を持つ凸多角形ができる。従って、マージを $(n + 1)$ 回以上行うことはできない。

　凸 $2 n$ 角形から $n$ 回マージを始め、凸 $n$ 角形を作るまでの具体例として、冒頭で紹介した動画があります。

　最後に、マージを $n$ 回行った後の点の数と真の直径数に注目します。ただし、ここで点の数を数える時、同一座標にある複数の点はまとめて1点として数えます。凸 $2 n$ 角形から $n$ 回マージを行うと、点の数は $n$ 個まで減っています。また、条件③を破っていないため、真の直径数は $n$ 個となります。

この問題を考えた背景

　この問題は、[2]の「エレガントな解答をもとむ」コーナーの問題2を解答するにあたり、核となったアイデアです。
　問題はこちらから確認できます。
　解説は[3]に記載されています。
　なお、本記事の内容は[3]の記載内容に一切依拠しておらず、ここで紹介した考え方は[3]では記載されていないことをここに付記します。