{{page>menu&nofooter&noeditbutton}} ====== Computational Geometry ====== Odkaz na zoom meeting: [[https://feectu.zoom.us/j/92268945460 | zde]] ===== News ===== * [[courses:cg:labs:3-ears|The third assignment]] is ready - I again apologize for the delay. * Lectures will be on-line in Czech language (there is no foreign student registered). * Výuka probíhá on-line podle rozvrhu přes systém zoom. Velmi doporučuji nainstalovat si nabízenou aplikaci na PC (dobře funguje i klient zoom pro android). Webový přístup nefunguje spolehlivě a má výrazně horší kvalitu. Odkaz "zoom meeting" na přednášky i na cvičení je níže a obdržíte jej i mailem. Přihlašujeme se svým user name pomocí sso v doméně feectu.zoom.us kliknutím na následující odkaz: [[https://feectu.zoom.us/j/92268945460 | Meeting]], heslo je druhé slovo názvu předmětu v češtině malými písmeny. ===== Summary ===== The goal of computational geometry is the analysis and design of efficient algorithms for determining properties and relations of geometric entities. The lecture focuses on geometric search, point location, convex hull construction for sets of points in d-dimensional space, searching nearest neighbor points, computing intersection of polygonal areas, geometry of parallelograms. New directions in algorithmic design. Computational geometry is applied not only in geometric applications but also in common database searching problems. ===== Prerequisities - what to know before attending the course ===== You definitely should know the fundamental sorting and searching algorithms, understand the concept of operational and memory complexity, and be able to write programs in %%C++%%. Knowledge of linear algebra, fundamentals of computer graphics would also be an advantage. ===== Seminars ===== - Seminars are compulsory (two absences are allowed). - Every student (or pair of students) is assigned a different topic for individual study. He/she prepares slides and presents them on the seminar. [[.:presentations:start|The topics available]]. - All students code the homework assignments (in C++). - Both, the presentation and the homework must be uploaded in the electronic form to the ([[https://cw.felk.cvut.cz/brute/ | upload system brute]]). * Sources of the presentation (.ppt, .odp, .tex + figures, ... more files in an archieve file). * The homework as a single .cpp file and/or the report file (.txt, .pdf,...) according to the homework handout. ===== Assessment ===== Conditions for awarding of the assessment: * Attending of the seminars (2 absences are tolerated without a necessity to excuse) * Oral presentation according to the plan * Presentation slides uploaded by 1 week after the presentation (later deliverable is penalized by -5 points) * Upload of the homework programs (later deliverable is penalized by -1 point penalty for every 24 hours after the deadline, but not more than -5 points penalty) * Minimum 25 points from seminars ===== Exam ===== Students who receive the assessment are allowed to take the exam. The exam focuses on theoretical knowledge from the lectures, seminars, and individual studies. The exam has a written part and an oral part. Additional positive or negative points can be obtained during the oral exam (in the extrema, fundamental lack of knowledge may yield to a failure (F)). For the exam, a maximum of 50 points can be awarded. A minimum of 25 points must be achieved for a passing grade: ^ ^ Total points ^ Minimum for passing ^ | **Seminars** ^ 50 ^ **25** | | - Presentation (oral + slides) | 10 | 4 | | - Homework assignments | 40 | 20 | | **Exam** ^ 50 ^ **25** | | - written | 40 | 20 | | - oral | 10 | 5 | The final grade is assigned according to the sum of seminars and exam points. ^ ECTS grade | Pass ||||| Fail | ^ ::: | **A** | **B** | **C** | **D** | **E** | **F** | ^ Points | 100-90 | 89-80 | 79-70 | 69-60 | 59-50 | 49-0 | ===== External links ===== * [[http://dcgi.felk.cvut.cz/en/study/academic_principles | Academic principles]], [[help:common:plagiarism_cheating | Plagiarism and cheating]] * [[http://dcgi.felk.cvut.cz | dcgi]] * [[https://www.fel.cvut.cz/en/education/rozvrhy-ng.B201/public/html/predmety/46/98/p4698606.html|Timetable - BE]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/predmety/46/98/p4698706.html| Rozvrh - B]] ===== Literature ===== * Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: [[http://www.cs.uu.nl/geobook/|Computational Geometry. Algorithms and Applications]], Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5 ([[https://aleph.cvut.cz/F/?func=item-global&doc_library=CTU01&doc_number=000688655|available in 10 exemplars in the CTU library located in National Technical Library building (NTK), Dejvice Campus, 5th floor, signature QA447 .C66 2008]]). [[http://www.cs.uu.nl/geobook/ | Web page]]. * [[http://www.cs.umd.edu/~mount/ | Mount, D.]]: [[http://www.cs.umd.edu/class/fall2016/cmsc754/Lects/cmsc754-fall16-lects.pdf | Computational Geometry Lecture Notes for Fall 2016 ]] - {{ :courses:cg:mount_-_computational_geometry_2016_fall_-_contents.pdf |Table of contents}} (older versions: [[https://www.cs.umd.edu/class/fall2016/cmsc754/Lects/cmsc754-fall16-lects.pdf | Fall 2016]], [[http://www.cs.umd.edu/class/fall2014/cmsc754/Lects/cmsc754-fall14-lects.pdf | Fall 2014]], [[http://www.cs.umd.edu/class/spring2007/cmsc754/Lects/comp-geom-lects.pdf | Spring 2007]], {{:misc:projects:oppa_oi_english:courses:ae4m39vg:mount_-_computational_geometry_2007_-_obsah.pdf|contents 2007}}) * O' Rourke, Joseph: [[http://maven.smith.edu/%7Eorourke/books/compgeom.html|Computational Geometry in C]], Cambridge University Press, 1st ed, 1994 or 2nd ed, 2000 * Preperata F.P.- M.I.Shamos: [[http://books.google.cz/books?id=gFtvRdUY09UC|Computational Geometry An Introduction.]] Berlin, Springer-Verlag,1985. ===== Lecturer & Instructor ===== [[http://dcgi.felk.cvut.cz/cs/members/felkepet|{{http://dcgi.felk.cvut.cz/_media/all/members/fullsize/felkepet-center.jpg?w=100&h=125|Petr Felkel}}]] \\ [[http://dcgi.felk.cvut.cz/cs/members/felkepet|Petr Felkel]]