计算几何算法（2019年 7月15日 - 29日开课）.pdf

计算几何算法 Algorithms in Computational Geometry 本课程将讲述在计算机科学领域中具有重要意义的一系列几何问题，其中包 括凸包计算，pareto 优化，平面扫描，多边形三角剖分，线性规划，最小包围圆， 点位置，voronoi 图，delaunay 三角化，最近距离对，正交范围搜索，等等。讨 论的对象为保证在很好的时间与空间复杂度内解决这些问题的数据结构与算法， 以及它们所代表的用以设计此类方法的通用技术。 教师风采 陶宇飞，男，41 岁，中国国籍，香港中文大学计算机科学与工程 系正教授，同时也是复旦大学客座教授。陶宇飞长期从事数据库算法的理论基础 研究。2002 年，他被授予香港青年科学家奖。2013 年和 2015 年，他分别两次在 数据库系统顶级会议 SIGMOD 上获得最佳论文奖。2018 年，他的一篇单作者的文 章在数据库理论顶级会议 PODS 上获得最佳论文奖。他于 2016 年被选为美国计算 机协会(ACM)杰出科学家（Distinguished Scientist)称号。他作为首席研究员 主持了 10 项香港研究资助局的 GRF 项目，并于 2016 年获得了 Google Faculty Research Award。 沙朝锋，男，43 岁，目前为复旦大学计算机科学技术学院 副教授。2009 年获复旦大学计算机软件与理论理学博士学位。主要研究兴趣为 数据挖掘、大数据分析、机器学习、社交网络分析等。主持或参与包括国家自然 科学项目等 10 余项，发表研究论文 50 余篇，获教育部自然科学二等奖 1 项。 课程设置 cai 采 课程性质：研究生课程（兼顾高年级本科生） 选课对象：计算机科学技术学院、大数据学院、软件学院、数学学院的研究生与 高年级本科生 学分：3 学分 学时：54 学时 授课校区： 邯郸校区 基础知识要求：选课学生应对本科程度的数据结构与算法有良好的掌握 上课时间：2019 年 7 月 15 日 - 29 日 课程助教：许燚，学号：17110240001， 邮箱地址：yxu17@fudan.edu.cn， 手机号：18717826769. 选课网址： http://register.fudan.edu.cn/p/publish/show.html?queryType=set&searchName=paidInfo.search &projectId=71738 课程内容 课程进度安排：2019 年 7 月 15 日至 7 月 29 日 日期 星期，时间 节次 上课内容 1-3 7 月 15 日 周一上午 凸包问题 1-2 7 月 15 日 周一下午 （续）凸包问题, MAXIMA 问 题 1-3 7 月 16 日 周二上午 （续）MAXIMA 问题 1-2 7 月 16 日 周二下午 平面扫描 授课教师 陶宇飞教授 陶宇飞教授 陶宇飞教授 陶宇飞教授 7 月 17 日 7 月 17 日 周三上午 周三下午 1-3 1-2 （续）平面扫描 7 月 18 日 周四上午 1-3 （续）多边形三角剖分，线 陶宇飞教授 多边形三角剖分 陶宇飞教授 陶宇飞教授 性规划 7 月 18 日 7 月 19 日 周四下午 周五上午 1-2 1-3 （续）线性规划 （续）线性规划 陶宇飞教授 陶宇飞教授 7 月 19 日 周五下午 1-2 最小包围圆 陶宇飞教授 7 月 22 日 周一上午 1-3 （续）最小包围圆 陶宇飞教授 7 月 22 日 7 月 23 日 周一下午 周二上午 1-2 1-3 期中考试 7 月 23 日 周二下午 1-2 7 月 24 日 周三上午 1-3 点面对偶，梯形分割，点位 陶宇飞教授 置 陶宇飞教授 （续）梯形分割，点位置 7 月 24 日 周三下午 1-2 voronoi 图，delaunay 三角化 陶宇飞教授 7 月 25 日 周四上午 1-3 （续） voronoi 图，delaunay 陶宇飞教授 点面对偶 陶宇飞教授 陶宇飞教授 三角化 7 月 25 日 7 月 26 日 周四下午 周五上午 1-2 1-3 最近距离对 陶宇飞教授 （续） 最近距离对，正交范 陶宇飞教授 围搜索 7 月 26 日 周五下午 1-2 （续）正交范围搜索 陶宇飞教授 7 月 29 日 周一上午 1-3 （续）正交范围搜索 陶宇飞教授 7 月 29 日 周一下午 1-2 期末考试 陶宇飞教授 考核方式 编程作业：25%； 课程中期测验：25%； 课程结束时测验：50% 参考教材 1、本课为香港中文大学计算机科学与工程系的研究生课程。最近一次开课 是在 2018 年春，并设立了下面的课程主页： http://www.cse.cuhk.edu.hk/~taoyf/course/5010/spr18/。 2、教科书之一： M. de Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer. 3、教科书之二： D. Mount. Computational Geometry. 此书可在作者主页上免费下载，网址： http://graphics.stanford.edu/courses/cs268-16-fall/Notes/cmsc754lects.pdf 。