短期共同研究

数理解析研究所講究録 872

短期共同研究

計算幾何学と 離散幾何学

京都大学数理解析研究所

1994 年 5 月

872

RIMS Ko たグα九σたα

Geometry Dlscrete

and

Geometry Computationa1

ユ 994 May,

Sciences Mathematical

for

工 nstitute

Research

Japan Kyoto,

University,

Kyoto

は し め に

この講究録は,短期共同研究「計算幾何学と離散幾何学」において発表された内容をまとめた ものてある 本研究は,広島大学の松本先生と北海道大学の日比先生に勧めて頂いて提案した短 期共同研究て,提案時の研究計画概要の目的の項ては,日比先生の案を元に以下のように記して いた

「近年,離散数学は純粋数学と応用数学の両面からの刺激を受けその研究活動か活性 化している 特に,計算幾何学,離散幾何学と呼ばれる分野は,代数幾何,超幾何函 数,トポロノーなとの純粋数学とともに,組合せ幾何,計算理論なとの応用数学とも 相互関係を有しなから急激に進展しており,Dlscrete&Computatlonal Geometry なとの雑誌か欧米諸国て出版され,国際研究集会も頻繁に開催されている しかし, 従来から我か国ては複数の分野に関連する領域の研究態勢は著しく貧弱てあると指摘

されており,とりわけ純粋数学と応用数学か交錯する領域の研究集会は絶無てある 我々は,純粋数学,応用数学なとの壁に捕れることなく,当該分野に興味を持つ研究 者か一堂に会し,自由な雰囲気て議論しなから,互いの問題意識を理解し,最近の研 究成果を確認するとともに,純粋数学と応用数学の境界領域ての斬新な視喧を探究す る,そのような機会を持ちたいと願うのてある 」

はたして,本研究か実施された3日間において,上記の目的を丸ごと全てというわけにはいか なかったか,十分に当初の目的を達成てきた これもひとえにこの研究に参加して頂いた方々の 熱心な講演 討論の賜てある

本研究の研究報告て,ほぼ以下のように共同研究概要を記した

「本短期研究(共同)は,純粋数学と応用数学の境界領域て幾何に関連した斬新な視 点を探求することを目的に行なわれ,両分野の研究者か参加して活発に発表 討論を 行ない,多大な成果を上げた 研究会は,Davld Avls(McGlll Unlverslty)の凸多面 体端呉列挙アルゴリズムの講演から始まり,両分野の共通部分てある凸多面体に関す る議論を行なった これに関連して,日比,今井他の発表かあり,凸多面体理論とア ルSリスムに関する新展開を図れた また,凸多面体に深く関連するアレンノメント の性質も調へ上げられ,それについては福田か有向マトロイトに関する講演を行なっ た また,本研究集会て集中的に討議されたことの1つに,曲面に埋め込まれたグ ラフの三角化の変換可能性かあり,根上,Dezaの発表なとを通して新しい成果か発 表された さらに,空間グラフ,結び目理論の計算機援用ノステム,計算幾何アルゴ リズムの画像処理への応用,組合せ幾何,計算幾何ての動作計画問題なとに関する講 演か行なわれ,それらに関する熱心な討議か行なわれた このように本短期共同研究 は非常に有益なものてあり,今後につなかる多大な成果を得た 」

また,本研究会は国際色豊かなものてあり,一部日本語に難のある研究者か是非とも内容を理 解したいということて,当日になって英語の講演をお願いした方もいた各講演の内容について

は,本講究録の論文等を参照されたい

このように有益な短期共同研究てあったのてその成果の講究録の刊行はもっと早く実現すへき てあったものを,研究代表者の遅滞によってここまて遅れてしまったことは懸悸に堪えない 一

方,間があいたことによって,本研究の次につながる成果が既に上がっている.研究代表者が把 握しているだけでも,

T Masada An Output Size Sensitive Algorithm for the Enumeration of Regular Triangu- lations Technzcal Report 94-01, Department of lnformation Science, University of Tokyo, January 1994

D Avis Generatmg Rooted Triangulations without Repetitions Technzcal Report No SOCS- 94 2, School of Computer Science, McGill University, February 1994

などがある. 今後もさらに様々な成果が得られていくと思われる. このような成果を導き出した

今井浩 (東京大学理学部)

短期共同研究

計算幾何学と離散幾何学

報告集

1993年5月17日{}19˜ 日

研究代表者 今井浩(Hlroshl Imal) 目次

1ディジタル画像における直線成分抽出のためのアルゴリズム

大阪電通大 浅野哲夫(Tetsuo Asano) 神戸商科大 加藤直樹(Naokl Katoh) 2 A C lmplementation of the Reverse Search Vertex Enumeration Algorithm

McGill University David Avis 3 Wagner s Theorem and Combmatorial Enumeration of 3-Polyt opes

東工大・理 Antome Deza

筑波大 福田公明 (Komei Fukuda) Temple U mversity Vera RDst a

4 A Solution for a Polygon Contunment Problem Usmg Sortmg X十Y 広大・理 Antonio Hernaiidez Barrera 5凸多面体をめぐる 数え上げ の組合せ論

北大・理 日比孝之(Takayuk1 Hibi) 6 Computational Geometry and Lmear Programmmg

東大・理 今井浩(Hiroshi lmai) 7 Discrete Geometry and D avenport-Schmzel Sequence

中央大・理工 今井桂子(Kelko Imaユ)

8 Extremal Problems and Ramsey Properties of Ball, Box or Orthant Containmg Many Points m Rd一And Combmatomcs of Permutations

早稲田大・理工 石神嘉康(Yoshiyasu lshigami) 9空間グラフについて

東女大・文理 小林一章(Kazuakl Kobayashi) 10閉曲面上のグラフの対角変形

横浜国大・教育 根上生也(Seiya Negaml) 11 Computational Construction of W-Graphs Associated with Hecke Algebras

奈良女子大・理 落合豊行(Mltsuyuki Ochiai) 12グラフの直線埋め込み問題について

東京理科大・理 徳永伸一(Shm。ichi Tokunaga) 131nt(P)∩Zη={0}^を満たすRn内の整凸多面体Pの双対多面体の体積の

上限について

東北学院大・教養 土橋宏康(Hiroyasu Tsuchihashi) 14埋め込まれた曲面の接続可能性

東大・理 吉田研秀(Kensyu Yoshlda)

1

16

30

35 41 49 65

79

82 103 108 144

150 158