Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Master
SUBJECT
| MMG1007 | Algorithmic Geometry |
| Teaching Staff in Charge |
Prof. VARGA Csaba Gyorgy, Ph.D., csvarga cs.ubbcluj.ro |
| Aims |
|
The purpose of the course is to familiarize the students with the notions and methods of the Computational Geometry, which can be applied in many areas of science, such as Applied Mathematics, Physics, Biology, Computer Science. Here we remark the applications of the Voroni diagrams in Astronomy, Molecular Physics, Biology and others. The students can use these notions in research and teaching as well. At the course and seminars we put the accent on the applications. |
| Content |
|
Courses
Course 1. Graphs - elements from the theory of graphs - planar graphs, Theorem of Euler Course 2. Line Segment Intersection - algorithm for computing the intersection of line segments - the algorithm’s complexity Course 3. Plane subdivison - Computing the overlay of two subdivisions - Computing the overlay of two polygons Course 4. Triangulation of polygons - Art Gallery Theorem - decompositions of the polygons in monotone pieces Course 5. Triangulation of monotone polygons Course 6. Convex Sets - Computing the convex hull of a set (algorithms of Jarvis and Graham) Course 7. Voronoi Diagrams - Voronoi Diagrams and basic properties - Construction of the Voronoi Diagrams using “divide et impera” method Course 8. Triangulation of a finite set of points - computing the Delaunay triangulation Course 9. The geometry of casting Course 10. Dynamic and kinetic Voronoi Diagrams Course 11. Higher Dimensions - Voronoi Diagrams in higher dimensions - Delaunay Triangulation - an application in astronomy Course 12. An application in Biology - the plants growth using the Voronoi Diagrams Course 13. An application of the Voronoi Diagram in describing the protein’s structure - computing the volumul of the protein Course 14. An application in Physics - the structure of the oxygen atom - an application in the Mechanics of Fluids Seminars Seminar 1. complexity of the algorithms, data structure Seminar 2. searching trees, B-trees Seminar 3. Triangulations of Polygons Seminar 4. Construction of the Sigma chain in the Voronoi Diagrams Seminar 5. Noneuclidian metrics, Poincare model Seminar 6. Affine diagrams, Weighted diagrams Seminar 7. Triangle with smallest Area Seminar 8. Intersection of Half Planes Seminar 9. the structure of proteins Seminar 10. dynamics of Fluids Seminar 11. The galaxies distribution Seminar 12. the structure of the oxygen atom Seminar 13. presentation of an essay (I) Seminar 14. presentation of an essay (II) |
| References |
|
1. CHEN JIANER, Computational Geometry: Methods and Applications, Texas A & M University, 1996.
2. BOISSONAT, J.-D.- YVINEC, M, Algorithmic Geometry, Cambridge, 1998. 3. T.H. COrmen, CH. E. LEISERSON, R.R. RIVEST, Introducere în algoritmi, Ediţia în limba română Computer Libris Agora, 2000. 4. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-dirichlet polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155–161, 1995. 5. M. Serrano1, G. D. Fabritiis2, P. Espaol1, E. G. Flekky3, and P. V. Coveney. Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A: Mathematics and General, volume 35, pages 1605–1625, 2002. 6. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-Dirichlet polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155–161, 1995. 7. D. Stora, P.O. Agliati, M.P. Cani, F. Neyret, and J.D. Gascuel. Animating lava flows. In Graphics Interface, 1999. 9. L. Zaninetti. The galaxies distribution as given from the Voronoi diagrams. In the Journal of Astronomy and Astrophysics, Italy. 10. F. M. Richards. The interpretation of protein structures: total volume, group volume distributions, and packing density. In In the Journal of Molecular Biology, volume 82, pages 1–14, 1974. 11. W. L. Roque and H. Choset. The green island formation in forest fire modeling with Voronoi diagrams. In the 3rd Center for Geometric Computing Workshop on Compuational Geometry, 1998. |
| Assessment |
|
Activity on Seminars 30%
Presentation of an essay 30% Oral final exam 40% |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |