HOME ] UP ] [ Syllabus ] Bulletin ] Handout ]


70240183 (Fall 2004): Syllabus

int(sqr(exp(9)))+8*76+sqr(-5*4+3!!*(2+1))+(int(arccos(-0!)))! = 70240183

-0!-1+2345-6*7*8-sqrt(9) = 2004


  • 课程简介

    • 来自不同领域的人,对“计算几何”一词的理解不尽相同。例如,从事几何造型方面研究的人,将曲线、曲面的设计与计算称为“计算几何”(《计算几何》,苏步青、刘鼎元编,上海科技出版社,1980年12月第一版)。在诸如《高等数据结构》和《算法设计与分析》等课程中,有的也会涉及到一些计算几何的问题。

    • 现代意义上的计算几何,借鉴算法理论、优化理论、几何学和组合学(尤其是图论)等学科的成果,旨在更为有效地解决各应用领域中的实际问题。Shamos的博士学位论文(M. I. Shamos. Computational Geometry. Ph.D. thesis, Dept. Comput. Sci., Yale Univ., New Haven, CT, 1978),标志着计算几何已经从算法设计与分析中分离出来,逐渐形成了一个独立的学科方向。从那时起,人们越来越清楚地看到,许多问题从本质上看都可以转化为几何问题。而且,从计算几何的角度来看,许多表面上毫不相干的问题,都可以统一为某个几何问题,甚至完全等价。因此,计算几何首先要研究的问题,就是如何将具体问题转化为具有一般性的几何问题,找出不同问题之间的共同点,并进而运用统一的方法来加以解决。计算几何讨论的对象限于离散的、有限的几何结构,但所涉及的问题范围很广,从计算机图形学、几何造型到地理信息系统,从计算机视觉到模式识别,从机器人学到计算机网络及通讯,从宏观的天文学到微观的分子生物学,都能够见到计算几何的身影。

    • 当然,正是由于其覆盖范围广泛,即使是在计算几何领域内部,不同人对她的理解和侧重点也差别很大。有些人强调几何算法的复杂度分析,有些人强调几何数据结构的具体设计;有些人直接将计算几何定义为“研究二维欧氏平面上离散几何结构的学科”,但计算几何的很多文献讨论的问题都是三维(甚至任意维)的,而另一些研究工作则已经不限于欧氏空间;......。

    • 本课程只有短短16周的时间,不应该(也不可能)对计算几何的每个方向都面面俱到,因此我们将结合若干实例,来讲解从实际问题到几何模型的转化、由此而得出的几何算法以及相关数据结构的设计与实现。我们将着重讨论二维欧氏平面上的几何结构,如凸包、三角剖分、Voronoi图、直线排列和子区域划分等。当然,对于有关的基础性理论(包括新近的发展),也将做一简要介绍。

    • 将本课程的重点放在上述方面的另外一个原因在于,授课教师与计算几何界的大多数研究者一样,都认为无论是就其本质还是目标而言,计算几何都应该是一门更加强调可构造性与构造过程的学科。

  • 教学目标

    • 本课程有三个教学目标:

    • 1. 使学生建立起对计算几何的总体性认识,从而在今后的研究工作中,能够尝试从计算几何的角度来思考、分析问题

    • 2. 掌握计算几何的基本概念与方法

    • 3. 懂得利用计算几何的有关数据结构及算法,去转化并解决实际的应用问题

    • 最后一点最为重要,这也是本课程强调动手实验的原因

  • 先修课程要求

    • 数据结构

    • 算法设计与分析

  • 主要知识点

    • Convex hull

    • (Delaunay) triangulation

    • Voronoi diagram

    • (Planar) arrangement

    • (Planar) configuration / dissection

    • (Planar) point location

    • (Planar) range search

    • Geometric Intersection

  • 作业

    • 本课程2004年秋季未能获得助教指标,作业将无法批改,故不记入最终成绩。

    • 尽管如此,还是希望并鼓励同学自己完成一定量的作业。

  • 课程大实验

    • 同学每三人自愿组合,围绕一个问题,以实验小组为单位合作完成实验

    • 同组内三人的实验得分相同

    • 第9周前,各组提交一份《实验选题报告》

    • 第13周周末前,约定各组的实验检查时间、地点

    • 第14周周末,按组检查实验

    • 第16周周末前,各组提交一份《课程实验报告》

  • 重要日期

    • 日期

      任务

      2004/11/07, 23:00 提交《实验选题报告》
      2004/12/12, 23:00 约定实验检查时间、地点
      2004/12/18 ~ /12/19 ~ 实验检查及答辩
      2004/12/30 笔试
      2005/01/02, 23:00 提交《课程实验报告》

 


TOP

HOME ] UP ] [ Syllabus ] Bulletin ] Handout ]

Copyleft (c) 2003-3002, Junhui Deng
Last updated on 05.30.2012