| Course code | CSCI5010 |
| Course title | Practical Computational Geometry Algorithms 實用計算幾何算法 |
| Course description | This course will discuss data structures and algorithms for solving fundamental problems in computational geometry with good theoretical guarantees. Topics covered include line-segment intersection, polygon triangulation, convex hull, linear programming, orthogonal range searching, point location, voronoi diagram, delaunay triangulation, and so on. 本科將討論為解決計算幾何中的基本問題，並具有良好的理論保障的數據結構和算法。涵蓋的主題包括線段相交，多邊形三角化，凸包，線性規劃，正交範圍搜索，點位置，Voronoi圖，Delaunay三角網，等等。 |
| Unit(s) | 3 |
| Course level | Postgraduate |
| Prerequisite | CSCI2100 or ESTR2102 or CSCI2520 |
| Semester | 1 or 2 |
| Grading basis | Graded |
| Grade Descriptors | A/A-: EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions. B+/B/B-: GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered. C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems. D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems. F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course. |
| Learning outcomes | At the end of the course of studies, students will have acquired the ability to 1. understand algorithms for solving fundamental problems in computational geometry. 2. learn and develop techniques for designing and analyzing computational geometry algorithms with non-trivial theoretical guarantees. |
| Assessment (for reference only) |
Essay test or exam ：60% Others ：40% |
| Recommended Reading List | Computational Geometry, Algorithms and Applications. By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. SpringerVerlag, 1997. Reference: Computational Geometry in C. By Joseph O’Rourke. Cambridge University Press, second edition, 1998 |
| CSCIN programme learning outcomes | Course mapping |
| Upon completion of their studies, students will be able to: | |
| 1. identify, formulate, and solve computer science problems (K/S); | T |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
T |
| 3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V); | T |
| 4. communicate effectively (S/V); |
T |
| 5. succeed in research or industry related to computer science (K/S/V); |
T |
| 6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S); | T |
| 7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V); | |
| 8. practise high standard of professional ethics (V); | |
| 9. draw on and integrate knowledge from many related areas (K/S/V); |
|
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |