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