[ HOME ] [ UP ] [ CGAA ] [ Demo ] [ Fall 06 ] [ Project ] [ Fall 04 ] [ Fall 03 ] [ Fall 01 ]

70240183 (Fall 2006)

-Fib(sqr(sqr(0!+1)))+2*sqr(3)+sqr(4)^5*67-8!/sqrt(9) = 70240183

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

  • 讲授时间

    • 每周一19:20~21:45

  • 课程进度计划

    • 周次 日期 倒计时 学时 内容
      1 09/18/2006 　 Syllabus
      　 Convex Hull
      　
      2 09/25/2006 　
      　
      　
      3 10/02/2006 　 N/A
      　
      　
      4 10/09/2006 　 Convex Hull
      　 Quiz #1
      　
      5 10/16/2006 　 Geometric Intersection
      　
      　
      6 10/23/2006 　
      　

      Art Gallery
      Triangulation
      Tetrahedralization
      　
      7 10/30/2006 　
      　
      　
      8 11/06/2006 　 Voronoi Diagram
      　
      　
      9 11/13/2006 　 Quiz #2
      　
      　
      10 11/20/2006 　 Delaunay Triangulation
      　
      　
      11/26/2006 　 Submit project proposal
      11 11/27/2006 　 Point Location
      　
      　
      12/03/2006 　 Take-home #1
      12 12/04/2006 　 Geometric Range Search
      　
      　 Windowing Query
      13 12/11/2006 　
      　 Arrangement
      　
      14 12/18/2006 　 Dissection
      　
      　
      15 12/25/2006 　 Free Talk
      　
      　
      16 01/01/2007 　 N/A
      　
      　
      01/[03~05]/2007 ~ 　 Project defence
      17 01/12/2007 　 Submit project report

  • 课程简介

    • 来自不同领域的人，对“计算几何”一词的理解不尽相同。例如，从事几何造型方面研究的人，将曲线、曲面的设计与计算称为“计算几何”（《计算几何》，苏步青、刘鼎元编，上海科技出版社，1980年12月第一版）。在诸如《高等数据结构》和《算法设计与分析》等课程中，有的也会涉及到一些计算几何的问题。
    • 现代意义上的计算几何，借鉴算法理论、优化理论、几何学和组合学（尤其是图论）等学科的成果和方法，旨在更为有效地解决各种应用领域中的实际问题。Shamos的博士学位论文（M. I. Shamos. Computational Geometry. Ph.D. thesis, Dept. Comput. Sci., Yale Univ., New Haven, CT, 1978），标志着计算几何已经从算法设计与分析中分离出来，逐渐形成了一个独立的学科方向。从那时起，人们越来越清楚地看到，许多问题从本质上看都可以转化为几何问题。而且，从计算几何的角度来看，许多表面上毫不相干的问题，都可以统一为某个几何问题，甚至完全等价。因此，计算几何首先要研究的问题，就是如何将具体问题转化为具有一般性的几何问题，找出不同问题之间的共同点，并进而运用统一的方法来加以解决。计算几何讨论的对象限于离散的、有限的几何结构，但所涉及的问题范围很广，从计算机图形学、几何造型到地理信息系统，从计算机视觉到模式识别，从机器人学到计算机网络及通讯，从宏观的天文学到微观的分子生物学，都能够见到计算几何的身影。
    • 当然，正是由于其覆盖范围广泛，即使是在计算几何领域内部，不同人对她的理解和侧重点也差别很大。有些人强调几何算法的复杂度分析，有些人强调几何数据结构的具体设计；有些人直接将计算几何定义为“研究二维欧氏平面上离散几何结构的学科”，但计算几何的很多文献讨论的问题都是三维（甚至任意维）的，而另一些研究工作则已经不限于欧氏空间 。
    • 总共48学时的本课程，不应该也不可能对计算几何的每个方向都面面俱到，因此我们将尽可能结合实例，来讲解从实际问题到几何模型的转化、由此而得出的几何算法 ，并设计和利用相关的数据结构加以实现。我们将着重讨论二维欧氏平面上的几何结构，如凸包、三角剖分、Voronoi图、直线排列和子区域划分等。对于有关的基础性理论（包括新近的发展），也将做简要介绍。
    • 将本课程的重点放在上述方面的另外一个原因在于，授课教师与计算几何界的大多数研究者一样，都认为无论是就其本质还是目标而言，计算几何都应该是一门更加强调可构造性与构造过程的学科。

  • 教学目标

    • 1. 使学生建立起对计算几何的总体性认识，从而在今后的研究工作中，能够尝试从计算几何的角度来思考、分析问题
    • 2. 掌握计算几何的基本概念与方法
    • 3. 懂得利用计算几何的有关数据结构及算法，去转化并解决实际的应用问题
    • 最后一点最为重要，这也是本课程强调动手实验的原因

  • 先修课程要求

    • 数据结构
    • 算法设计与分析

  • 主要知识点

    • Convex hull
    • (Delaunay) triangulation
    • Voronoi diagram
    • (Planar) arrangement
    • (Planar) configuration / dissection
    • (Planar) point location
    • (Planar) range search
    • Geometric Intersection

  • 作业

    • 本课程2006年秋季未能获得助教指标，作业将无法批改，故不记入最终成绩。
    • 尽管如此，还是希望并鼓励同学自己完成一定量的作业。

  • 课程大实验

    • 同学每三人自愿组合，围绕一个问题，以实验小组为单位合作完成实验
    • 同组内三人的实验得分相同
    • 第11周之前，各组完成大实验选题并提交《选题报告》
    • 第15周之前，约定各组的实验检查时间、地点
    • 第16周，按组检查实验
    • 第17周周末前，各组提交一份《课程实验报告》

　

TOP

[ HOME ] [ UP ] [ CGAA ] [ Demo ] [ Fall 06 ] [ Project ] [ Fall 04 ] [ Fall 03 ] [ Fall 01 ]

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