カーペンターの法則の問題

大工の法則問題は離散幾何学の問題であり、次のように表現できます。単純な平面多角形を、そのすべての頂点が凸状の位置にある位置まで連続的に移動させ、その途中で辺の長さと単純さを維持できるか?これに密接に関連する問題は、任意の非自己交差多角形チェーンを、やはり辺の距離を維持し交差を回避する連続変換によって直線化できることを示すことです。

両方の問題は、Connelly、Demaine、Rote (2003) によって解決されました。

この問題は、金属製の巻尺の改良により使われなくなった19世紀から20世紀初頭にかけて大工の間で人気があった、複数の関節を持つ木製の定規にちなんで名付けられました。

組み合わせ論的証明

その後、彼らの研究に対して、イリアナ・ストレイヌはロボットアームの動作計画の用語で定式化された簡略化された組合せ論的証明を提供した。オリジナルの証明とストレイヌの証明は両方とも、入力の非拡大運動、つまり2つの点が互いに向かって動かないような連続的な変換を見つけることによって機能する。ストレイヌのバージョンの証明は、尖った疑似三角形分割を形成するために入力に辺を追加し、このグラフから追加された凸包の辺を1つ削除し、残ったグラフには距離がすべて減少しない1パラメータの運動族があることを示す。このような運動を繰り返し適用することで、最終的にはそれ以上の拡大運動が不可能な状態に到達するが、これは入力が真っ直ぐまたは凸になった場合にのみ起こり得る。

Streinu と Whiteley (2005) は、この結果を紙折りの数学に応用し、紙の単純な非自己交差運動のみを使用して、任意の単一頂点折り紙形状を折る方法を説明しています。本質的に、この折り畳みプロセスは、長さが π より小さい多角形を凸状にする問題の時間反転バージョンですが、ユークリッド平面ではなく球面上にあります。この結果は、Panina と Streinu (2010) によって、辺の長さが 2π より小さい球面多角形に拡張されました。

一般化

ジョン・パードン (2009) は、カーペンターの法則の問題を、修正可能曲線に一般化しました。彼は、修正可能なすべてのジョルダン曲線は、その長さを増やすことなく、また任意の 2 つの点間の距離を減らすことなく、凸曲線にできることを示しました。彼がまだ高校生だったときに行われたこの研究により、パードンは 2007 Intel Science Talent Search (Cunningham 2007) で 2 位の賞を受賞しました。

参照

曲線短縮フロー、平面上の閉曲線の連続的な変換で、最終的に曲線を凸状にする。

参考文献

Connelly, Robert ; Demaine, Erik D. ; Rote, Günter (2003)、「多角形弧の直線化と多角形サイクルの凸状化」(PDF)、Discrete and Computational Geometry、30 (2): 205–239、doi : 10.1007/s00454-003-0006-7、MR 1931840暫定版は、 2000 年に開催された第 41 回コンピュータサイエンスの基礎に関する年次シンポジウムで発表されました。
カニンガム、エイミー（2007年3月17日）「次世代」、サイエンスニュース：166。
Streinu, Ileana (2000)、「平面非衝突ロボットアーム動作計画への組み合わせアプローチ」、第 41 回コンピュータサイエンスの基礎に関する年次シンポジウムの議事録、IEEE コンピュータ協会、pp. 443–453、doi :10.1109/SFCS.2000.892132、MR 1931841、S2CID 9420124
パニーナ、ガイアネ、ストレイヌ、イレアナ（2010）、「単一頂点折り紙の平坦化：非拡張ケース」、計算幾何学：理論と応用、43（8）：678–687、arXiv：1003.3490、doi：10.1016/j.comgeo.2010.04.002、MR 1931841
パドン、ジョン(2009)、「単純な閉曲線の展開について」、アメリカ数学会誌、361 (4): 1749–1764、arXiv : 0809.1404、doi :10.1090/S0002-9947-08-04781-8、MR 2465815、S2CID 230031。
Streinu, Ileana ; Whiteley, Walter (2005)、「単一頂点折り紙と球面膨張運動」、離散幾何学と計算幾何学: 日本会議、JCDCG 2004、東京、日本、2004 年 10 月 8 日～11 日、改訂選定論文、Lecture Notes in Computer Science、vol. 3742、Springer-Verlag、pp. 161～173、MR 2212105

外部リンク

Erik Demaine のページには、いくつかのリンクに適用された直線化動作のアニメーションが掲載されています。