UMass Lowell Computer Science 91.504UMass Lowell Computer Science 91.504
           Advanced AlgorithmsAdvanced Algorithms
         ComputationalComputationalComputationalComputational  GeometryGeometryGGeometryeometry
            Prof. Karen Prof. Karen DanielsDaniels
              SpringSpringSpringSpring, , 2010201020102010
              Lecture 1Lecture 1
           CICICCourse ourse IInnttttrorodddducuctitittiionon
         Course IntroductionCourse Introduction
            What is What is 
        ComputationalComputationalComputationalComputational  GGGeometry?Geometry?eometry?eometry?
                                               Advanced AlgorithmsAdvanced Algorithms
                                               ComputationalComputationalComputationalComputational  GeometryGeometryGeometryGeometry
                                  Computer Computer 
                                  GraphicsGraphics                       Design                               Analyze
                                                             feasibilityfeasibility,, estimation, optimization problems estimation, optimization problems                       Covering for Covering for 
            VVVViiiisualizationsualizationsualizationsualization                                          for for                                                               Geometric Geometric 
                                                         covering, assignment, clustering, packing, layout, covering, assignment, clustering, packing, layout,                  ModelingModeling
                                                                                        geometric modelinggeometric modeling
            Data Mining,  Data Mining,  
            Clustering, for Clustering, for 
            BioinformaticsBioinformatics
                                                                                              Apply                                                              TTopological Invariant opological Invariant 
                                                                                                                                                                 Estimation for Estimation for 
                                                                                                              Meshing Meshing                                    Geometric  Modelin
                                                                                                                                                                 Geometric  Modelingggg
                                                                                                              for for 
                                                                                                              Geometric  Geometric  
                Packing for Packing for ManufacturingManufacturing                                            Modeling Modeling                          CADCAD
                                                                       CourteCourtesy sy of of CadeCadennccee Design System Design Systemss
                                          Typical ProblemsTypical Problems
           ••    binbinbinbin  packingpackingppackingacking                                     ••    maintaininmaintainingggg line  line 
           ••    VoronoiVoronoi diagramdiagram                                                        arrangementsarrangements
           ••    simplifying simplifying                                                        ••••  polygonpolygonpolygonpolygon  
                 polygonspolygonspolygonspolygons                                                     partitioningpartitioning
           ••    shape similarityshape similarity                                               ••    nearest neighbor nearest neighbor 
                                                                                                      searchsearch
           ••    convex hullconvex hull                                                         ••    kdkd--treestrees
           SOURCESOURCE: : Steve Skiena’Steve Skiena’ss  Algorithm Design Manual Algorithm Design Manual 
           (for pr(for problem oblem descriptidescriptions, see ons, see graphics graphics gallgalleery at ry at http://www.cs.sunysb.edu/~algorith))