[ HOME ] [ UP ] [ Syllabus ] [ Bulletin ] [ Handout ] [ Evaluation ]

70240183 (Fall 2003): Syllabus

-1+2*(2!+3!)!*(4!+5!+6!+7)+7*7*7*8 = 70240183

0!+1234+5!-(6-78)*9 = 2003

  • 授课安排

    • 每周三晚7:20-9:45pm
    • 四教4403

  • 课程进度计划

    • 周次

      日期

      内容

      1

      2003/09/17

      　

      Ch00. Introduction

      　

      2

      2003/09/24

      　

      Ch04. Convex Hull

      　

      3

      2003/10/01

      　

      (National Day)

      　

      4

      2003/10/08

      　

      Ch04. Convex Hull

      　

      5

      2003/10/15

      　

      Ch12. Geometric Intersection

      　

      6

      2003/10/22

      　

      Ch14. Triangulation of Simple Polygons

      　

      7

      2003/10/29

      　

      　

      Ch11. Voronoi Diagram

      8

      2003/11/05

      　

      　

      9

      2003/11/12

      　

      Ch17. Point Location

      　

      10

      2003/11/19

      　

      　

      Ch18. Geometric Range Search

      11

      2003/11/26

      　

      　

      12

      2003/12/03

      　

      Ch19. Delaunay Triangulation

      　

      13

      2003/12/10

      　

      Ch01. Arrangement

      　

      Ch02. Semi/space

      14

      2003/12/17

      　

      Ch13. Planar Arrangement

      　

      15

      2003/12/24

      　

      Ch03. k-Sets & k-Levels

      　

  • 课程简介

    • 来自不同领域的人，对“计算几何”一词的理解不尽相同。例如，从事几何造型方面研究的人，将曲线、曲面的设计与计算称为“计算几何”（《计算几何》，苏步青、刘鼎元编。上海科技出版社，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

  • 作业

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

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

  • 课程实验

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

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

    • 第9个星期天之前，各组提交一份《实验选题报告》

    • 第16个星期天之前，约定各组的实验检查时间、地点

    • 第17周，按组检查实验

    • 第17个星期天之前，各组提交一份《课程实验报告》

  • 重要日期

    • 日期

      任务
      2003/11/16, 23:00 提交《实验选题报告》
      2004/01/04 约定实验检查时间、地点
      2004/01/07 ~ 2004/01/09 ~ 实验检查及答辩
      2004/01/11, 23:59 提交《课程实验报告》

　

TOP

[ HOME ] [ UP ] [ Syllabus ] [ Bulletin ] [ Handout ] [ Evaluation ]

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