[ 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