这页说计算几何(之关联见苏步青大师等下面确立计算机图形学”),这领域主要参考书是下面台湾主席的导师的《计算几何导论》-其序言说‘随着许多技巧同组合数学、组合几何代数几何相互影响,计算几何达到相当完善水平’,而这视频5分处说海南琼州大学的导师钟集教授和徐利治合创中国组合数学研究会,并看这里见钟集老师是我国计算开拓者,他还做为“几何学科代表和代数、分析学科代表组成我国高自考第一届全国委员会正副主席。这《计算几何导论》的目录只冠于3个人名:2个是基于美国科学院副院长组合数学大师Graham发表于IPL杂志的仅1页余却具非常影响的论文Jarvis的这IPL论文(海南琼大也在IPL发表论文但好根基早就已筑铺上很多层)。关于前面说的计算几何的技巧主要是逼近论、计算数学方面的,就如这里出7位校长全球罕见的华中科技大学机械工程的82、83、84、85级研究生教学试用的胡瑞安主编1987年出版的《计算机辅助几何设计》其各章就要么是插值、逼近或样条曲线等几乎都属于逼近论,其广义来说还包括计算机视觉而我的导师钟集教授几何书就被中国计算机学会理事长高文的《计算机视觉》引用。再如中国计算机学会理事长唐泽圣等的《计算机图形学基础》的第三章二维图形生成技术主要讲样条曲线等函数逼近论的理论技术、第六章三维形体的表示主要用样条曲面等函数逼近论的理论技术-还有国际计算机协会中国理事会首届理事长孙家广许隆文1986年《计算机图形学》-中国图学学会第4届理事长唐荣锡汪嘉业1990年出版的《计算机图形学教程》也差不多(这是因1982年成立了全国计算几何协作组成员有苏步青、梁友栋、金通洸、刘鼎元、汪嘉业、唐荣锡、孙家旭、齐东旭等并当同时确立“计算机图形学的造型和绘制是‘计算几何协作组’工作的两个主要内容-计算机图形学的目的是绘出具有真实感的图形-正如刚见吉大只讲计算机图形学、组合数学的郭晓新教授在12页说计算机图形学=几何+绘制,如此我不仅有这组员中苏步青刘鼎元的《计算几何》、组员孙家旭独撰的《样条函数与计算几何》、组员齐东旭合撰的《样条函数方法》也有组员唐荣锡汪嘉业的上面《计算机图形学教程》、组员梁友栋石教英1987年翻译出版的Rogers的《计算机图形学的算法基础》,梁友栋金通洸是上面浙大学派的缔造者并该校的中国工程院常务副院长潘云鹤院士在其后出版《计算机图形学》我也有;国外的我还有刘慎权翻译的Angell的《计算机图形学实用导引》),关于协作组中汪嘉业是山东省计算机学会第2届理事长、第1届理事长是郑玉林只有一篇论文并他的第1个可查研究生也是做这方面的、第3届理事长马绍汉就做下面组合算法等我有他1988年出版的《图算法》并他还和我国哈密顿图开创者刘振宏大师合作《离散最优化算法》-这前3届理事长都是山大数学系毕业留校的、第4届是山东工业学院教师和最近的第5是我国这方面先驱刘慎权的博士(第1届的4个副理事长周澄华 吕家俊 蒋富瑞 丛树福也全部都是第2届的列在上面汪嘉业 马绍汉后面的副理事长-看来山东计算机被这方面主宰,中国计算机图形学贡献奖中第8位以前的得主就是上面这些开拓元老-石教英写了一本科学计算可视化-内容简介说为计算机科学与工程、应用数学等师生用-正如其定义为:“可视化是一种计算方法,…”--其地位如《计算机辅助设计与图形学学报》的内容包含可视化、VLSI设计)。

关于计算机图形学,也与图学、画法几何也很有紧密关系。总之,我的导师钟集教授在这些与几何图学相关学科领域有贡献是因如从事几何的钟集教授、代数1984年已当北京大学校长丁石孙教授、分析的王斯雷教授3人就1985年组成全国高自考委正副主席,就如从广义来说引用海南琼州大学的导师钟集教授的著作的前面说的《计算机视觉》及图象处理就属于计算机图形学。这页下面主要简介的计算组合几何既有计算几何的某些共性但主要是由下面这些特定领域交叉而产生的学科,如浙江大学应用数学系设有计算几何与计算机辅助几何设计方向等,就如搜Greg Turk数学越来越不够用我就曾读样条函数、逼近论、数值分析、计算数学、计算几何、计算机辅助设计、计算机图形学、计算机视觉等当然有些不深读还有这里的很多数学当然专题是谁都读不完的。刚见这Turk的博士王华民弃教职投身万亿的计算机图形学产业;而引用我导师的书的计算机视觉也已是大产业):

 

第一、组合几何和计算几何

台湾计算机学会主席、中兴大学校长、亚洲前4个国际计算机学会院士李德财的导师Franco PreparataMichael I. Shamos的《计算几何导论》序言说‘随着许多技巧同组合数学、组合几何代数几何相互影响,计算几何达到相当完善水平’,而这视频5分处说海南琼州大学的导师钟集教授和徐利治创办中国组合数学研究会,并看这里见钟集老师是我国计算开拓者,他还做为“几何代表和代数、分析代表组成我国高自考第一届全国委员会正副主席。这《计算几何导论》的目录只有出现3个人名-组合数学大师Graham的这IPL1页余却有非常影响的论文Jarvis的这IPL论文19世纪的Voronoi(海南琼州大学也IPL发论文但它是这里第一段最后不及6的哈图)。

计算几何的应用已很广如Ivor D. FauxMichael J. Pratt1979年出版的这本330页书《Computational geometry for design and manufacture用于设计和制造的计算几何》-评论这书的A. R. Forrest正是计算几何先驱(苏步青大师的《计算几何》的参考文献中最多2个人是这Forrest10篇、苏步青大师的11篇中第1篇是他自己的《高等几何讲义-但上面中国计算机学会理事长高文的《计算机视觉》只引用海南琼州大学的导师钟集教授的《高等几何》一书)。

这交叉学科领域的主要分支方向有:“Discrete Geometric AnalysisStructuresAlgorithms”和《Discrete and Computational geometry:组合算法方面》以及Combinatorial Geometry等。

这里1993年曾邀请海南琼州大学去合作的我国渐近和逼近论先驱徐利治大师为首和他的3个学生王仁宏、梁学章、周蕴时合作研究的"数值逼近与数值积分"获国家自然科学三等奖并其中的梁学章等运用图论方法较好地解决了二元四次样条插值问题,提出了一些有效的实现空间B样条曲面和NURBS曲面间光滑拼接的充分性条件和算法和梁学章获第八届“几何设计与计算杰出贡献奖(这国家奖中另一的周蕴时教授也已第九届“几何设计与计算杰出贡献奖,而国家奖中的王仁宏-这里见他的前5个博士全都早就已是计算机信息软件学院正院长全都早就已是计算机权威(并看王仁宏最近出版的《计算几何教程》一书目录-见它完全是一本逼近论书籍)。王仁宏在这个视频开头就说60年以后吉林大学就决定我做徐老师的助手-开始说呢做徒弟,那时师傅带徒弟,后来不做徒弟作助手,从那时开始我和徐老师就已直搞在一起-接着是北京大学本科毕业并跟1986年担任校长的伍卓群做研究生的郑斯宁说伍卓群校长跟我多次说过他的本科毕业论文就是徐利治先生指导的,所以对他有很大的影响,如此伍卓群成为吉林大学的校长兼著名数学家、而王仁宏教授呢在这里第一段成为当之无愧的国际大师,等等众多杰出徒弟。其实徐先生在西南联大读书时的才华可能已是全校最杰出的-我有足够说服力的理由-也可参看这里开头说:徐利治是华罗庚先生在西南联大时期的助教。并华罗庚曾说过:“在我的众弟子中,徐利治的研究领域是最广的,思想也是最活跃的”等等)。

这个Computational Geometry Books计算几何书籍”推荐网:它的第4本书是《Algorithms in Combinatorial Geometry组合数学几何的算法》-也即这本423页的《Algorithms in Combinatorial Geometry.

这方面可参考:现代控制理论奠基人之一Lev Pontryagin的博士Vladimir BoltyanskyMark Krein的博士Israel GohbergMGP)合写的《Results and problems in combinatorical geometry》( 有书评:Amer. Math. Monthly 94 (1987), no. 4, 391–392.

国际数学联盟秘书长Martin Grotschel、国际数学联盟主席Laszlo Lovasz以及Alexander Schrijver 1988年撰写的Geometric algorithms and combinatorial optimization(此书前面是讲一些几何算法和优化理论,第789章的几乎每一节都结合图论讲它们在各方面各具体领域的发展或应用,如在第8章讲到邀请海南琼州大学去澳大利亚合作的管梅谷校长开创的中国邮路问题时说:this optimization problem which is important in practice and related to matching theory etc.

历史上十大天才之一的Paul Erdos , Peter M. Gruber , Joseph Hammer1989年撰写的“Lattice Points“。

现代组合数学奠基人Gian-Carlo Rota和他的博士Henry H. Crapo合撰1970年出版的289页的On the Foundations of Combinatorial Theory: Combinatorial Geometries论组合理论的基础:组合几何

Herbert Edelsbrunner1987年撰写的Algorithms in Combinatorial GeometryJacob E. Goodman写这书的书评Amer. Math. Monthly 96 (1989), no. 5, 457–460.)(Edelsbrunner的导师Hermann Adolf Maurer和撰写多本离散几何书的宗传明教授是师兄弟).

Jürgen BokowskiBernd Sturmfels合撰的《Computational Synthetic Geometry》( Jürgen Bokowski是后者的Bernd Sturmfels的导师;Bernd Sturmfels的另一导师Victor Klee也翻译Hugo HadwigerHans Debrunner,下面组合几何早期名著《Combinatorial geometry in the plane》). 

János Pach和杜克大学Pankaj K. Agarwa合撰1995年出版的Combinatorial Geometry

Joseph O'Rourke教授的网页见他1994年出版Computational Geometry in C 计算几何: C语言描述》1997年又和“离散和计算几何”杂志创刊主编J. E. Goodman出版991页的《Handbook of Discrete and Computational Geometry离散和计算几何手册》

Ketan Mulmuley独撰的447页“Computational Geometry: An Introduction Through Randomized Algorithms”;

Kurt Mehlhorn独撰的“Data structures and algorithms3Multidimensional searching and computational geometry”,“1Sorting and searching排序和搜索”,“2Graph algorithms and NP-completeness图论算法和NP完备性”;

计算机鼻祖独立指导的已当选美国三院院士的博士Leonidas Guibas独撰的60多页的Basic algorithms and combinatorics in computational geometry计算几何中的基本算法和组合数学;

第七届中美工程技术研讨会主席(全国政协副主席徐匡迪只向他一人颁发荣誉证书)、美洲中国工程师学会总理事长、美国玉山科技协会理事长、成立于1857年坐落于硅谷San Jose State University电机系系主任-成为全美国200多个电机系最年轻的一个系主任的陈润吾Ray Ruen-Wu Chen教授在1988年发表的“Graph theory in the context of VLSI and CAD,等等。

1995James D. Foley / Andries van Dam / Steven K. Feiner / John F. Hughes出版的1175Computer graphics in C: principles and practice2最近被上面中国计算机学会理事长唐泽圣等翻译-就如其说这是计算机图形学领域的一部经典之作-显然这大部头巨著只适合参考(第2作者Andries van Dam曾是国际图形图像协会第一届秘书长,我更早就有唐泽圣、孙家广等译1986年出中文版的这前2作者James D. FoleyAndries van Dam合撰的《交互式计算机图形学基础

组合几何和计算几何结合方面的最近616页书籍《Combinatorial and computational geometry

组合几何和计算几何结合方面的最近的学位论文:“Combinatorial and computational geometry”,“Computational and combinatorial geometry”等。

1978年的博士论文做“Travelling Salesman Problem旅行商问题也就是最小哈密顿圈问题的Selim Akl1993年撰写Parallel Computational Geometry并行计算几何》一书(它第3章是凸包,上面面《计算几何导论》第34章都是凸包;它第4章是互交,《计算几何导论》第7章是互交它第5章是几何查找,《计算几何导论》第2章是几何查找;第7章是邻近问题,《计算几何导论》第56章都是邻近问题,等,当然还有深广度和选材等问题。他毕业的第2年就发表很著名的哈密顿圈图论文,他的导师也是计算几何先驱).

博士论文做平面有向图的Giuseppe Di BattistaPeter EadesRoberto TamassiaIoannis Tollis 合撰的397页《Graph Drawing: Algorithms for the Visualization of Graphs图形绘制:图形可视化算法》(这书第1页给出的最先2个与本书最相关的关键词是:Computer graphics计算机图形学,Graph theory图论。可参考这个Graph Drawing,或看这里对Graph Drawing的解译-可知它就是海南琼州大学曾在某些领域世界领先的图论的图而非图象即不涉及颜色深浅等; 此外这书的第3、第4作者Roberto TamassiaIoannis Tollis都是上面1990中文版《计算几何导论》的第一作者Franco Preparata的博士--但其实Franco Preparata的博士中的他俩和这里1997年成为亚洲第4个当选国际计算机学会院士的李德财校长可能都不如他的1995年才博士毕业的女Nancy Amato最近很厉害-如她从伊利诺大学香槟分校毕业分去德州农工大学多年后又回来并成为计算机系系主任[伊利诺大学香槟分校也是亚洲第1、第2个当选国际计算机学会院士的刘炯朗、姚期智-当然也还有李德财工作和读博士的大学,如看计算机工程排名-一直来都在美国前5、上面Turk王华民的大学也在前8]-但一个女孩大概大概差不多就行了-但她却很特别如她的简历见她在斯坦福大学获得数学和经济学2个本科学位并跟1995年图灵奖得主Manuel Blum读硕士却在1995年获得上面Franco Preparata博士)

还有,这里最后段的写了很多组合数学图论书的清华大学计算机系第一个博士的导师卢开澄教授周培德著的《计算几何:算法分析与设计》-不过内容有些差别。

这里第2段的人工智能之父明斯基和机会很少的多年前曾邀请海南琼州大学去的徐利治教授的师弟Seymour Papert合撰出版Perceptrons: An Introduction to Computational Geometry感知器:计算几何导论(我有这1988的扩充版).

欧洲大陆第一大学这个计算几何网的最下面见它只推荐1个杂志(刚见它再推荐一个刚创办的杂志)即它推荐的第一个是Journal of Computational Geometry并这杂志的右下角见它是Platform and Workflow by OJS/PKP和见主编是Ken ClarksonKen Clarkson就是1987年已发表计算几何论文的Kenneth L. Clarkson也即姚期智院士的1984年已毕业的博士并看到他的个人主页说他是IBM技术负责人和见他列出的杂志中第一个正是前一行由OJS/PKP做相关负责的杂志),而这里仅一个出版社的十几个杂志中海南琼州大学曾担任它们多个杂志主编并右下角见也是Platform and Workflow by OJS/PKP(当然现在状况已如这个杂志的15个美国院士级大师已全部退出编委会--可要知以前如看这里中下部分就见前行说的这十几个杂志的很多来自世界各国的审稿专家都是由海南琼州大学做出决定和邀请-但每届只任职2个杂志这样便认识得更多更细些并我担任的一百多个杂志编委中确实正如这里所说的只选这出版社至多2个杂志)。看这个“计算几何网”的右上角见About this site见它说2007年至2021年由Monique Teillaud维护和hosted by INRIA即由法国国家计算机及自动化研究院主持(而维护者Monique Teillaud1991年博士毕业并个人网见是INRIA的研究主任以及这个网见其1981年进世界第4的巴黎高师已指导40多的博士博士后是中心副主任算这学科世界权威)此后的2021年以后由ETH Zürich主持即由除岛国英国外的爱因斯坦的母校“欧陆第一名校”苏黎世联邦理工学院主持--仅一个网站用得了扯那么远吗(且前面从事计算几何的台湾计算机学会理事长中央计算机研究所所长中兴大学校长Der-Tsai Lee李德财院士和年轻华裔Jinhui Xu合作主编International Journal of Computational Geometry and Applications由得到陈省身大师、杨振宁大师、李政道大师等高标准赞誉的新加坡世界科技出版社1991年已创刊2012影响因子仍不到0.1-但这是啥呢如这里第一段见海南琼州大学是创刊编委的杂志2012影响因子超过1.2或就如这里海南琼州大学担任多个1区杂志编委的第一段所见。因此这欧陆第一名校似乎只信欧美主编,不过这杂志就是仅管理编委3:博士做Geometric GraphsMorin1991年巴黎大学博士Teillaud、博士做Graph DrawingWood并全在名校指导出博士---其实亚洲人当选国际计算机学会院士的最先4人中有他李德财、姚期智及姚的导师再另一是日本人-并这4计算机院士都是组合数学图论专家)。

 

第二、计算组合学和计算图论

关于这学科可参考和海南琼州大学合作多篇论文的清华大学数学系党委书记胡教授的著名论文《计算组合学和计算图论等。

这学科的参考书有:胡教授上面论文参考的加拿大科学院院士David M. Jackson和他的博士Ian Peter Goulden的《 Combinatorial enumeration  Gian-Carlo Rota作序言, .John Wiley \& Sons, Inc., New York, 1983.

丁大学副校长Ewan Stafford PageLeslie Blackett Wilson的《An introduction to computational combinatorics》, Cambridge University Press, New York, 1979

数学大师Georg Polya,胡教授的合作者的Ronald C. Read合撰的《Combinatorial enumeration of groups, graphs, and chemical compounds》,由Dorothee Aeppli翻译为1987年英文版

徐利治先生和蒋茂森 朱自强教授合撰的《计算组合数学》

MITRichard P. Stanley院士在90年代撰写的这领域著作也已受各国所重视。

 Georgy P. Egorychev著撰的Integral representation and the computation of combinatorial sums

还可参考西南联大数学系系主任1962年任清华大学副校长、兼中国计算数学学会第一届理事长赵访熊教授组织北京大学清华大学编写的《计算方法》

Gary Theodore Chartrand低一届的师弟Medhi Behzad, Vadim Georgievich Vizing,(叶宏博  王建芳  张忠辅发表在《科学通报》的“TOTAL CHROMATIC NUMBER OF GRAPHS OF HIGH DEGREE 

Marvin D. Marcus的博士S. Gill Williamson撰写的479Combinatorics for computer sciencecomputer science很大程度上就是computational science

S. Gill Williamson又和Edward A. Bender合撰《Foundations of applied combinatorics

 

第三、组合算法和图论算法:

这领域的主要参考书:

1993年的图灵奖获得者Juris Hartmanis的博士Edward M. ReingoldJürg NievergeltNarsingh Deo合撰的《Combinatorial Algorithms: Theory and Practics合算法:理论与实践》。我有1977年英文版;

哈佛博士Shimon Even的《Algorithmic combinatorics算法组合论》,1973年(Shimon Even也独撰《图论算法》

圣地亚哥分校计算机科学系主任Te Chiang Hu胡德强的《Combinatorial Algorithms组合算法》,我有的是1982年英文版(这书每章都有许多参考文献,被引文献最多的是他自己之外,其次就是被誉为“算机鼻祖”、“法的上帝至今历史最年轻的计算机诺贝尔奖图灵奖获得者Donald E. Knuth大师,并最后章有Donald E. Knuth独撰的书Combinatorial Algorithms组合算法Vol. 4, Addison-Wesley, 19。我们知道Donald E. Knuth70年代中期已出版了3卷,这第4卷听说也完成了初稿,但一直不见正式出版

美国三院院士Christos Papadimitriou和普林斯顿大学Kenneth Steiglitz院士合撰的630页的《组合最优化》   

最后说2个日本大师的图论算法著作:亚洲第3个当选ACM(国际计算机协会)院士Takao Nishizeki为第一作者的1988年出版的《Planar Graphs: Theory and Algorithms平面图:理论与算法》;亚洲6个当选ACM(国际计算机协会)院士Toshihide Ibarak校长和他的博士Hiroshi Nagamochi合写最近出版的375页的Algorithmic Aspects of Graph Connectivity图连通性的算法方面