Week #10 | |

Pedro Ribeiro - DCC/FCUP |

*Computacional Geometry Data Structures and Primitives*:- I know how to represent
**points**,**lines**and**simple polygons** - I know how to compute
**distances**and**intersections**in simple geometrical objects - I know how to compute if a
**point is inside a polygon** - I know how to compute the
**area of a polygon**using the**shoelace formula** - I know and understand the
**ccw**(counterclockwise) primitive - I know how to compute if a
**polygon is convex** - I know what a
**convex hull**is and I know an O(n log N) algorithm to compute it (ex:**Graham's Scan**) - I know the concept of divide and conquer in the
**closest pair of points**classical algorithm

- I know how to represent

- Chapters 29 and 30 of Competitive Programmer's Handbook book
- Chapter 7 of the Competitive Programming book
- Topcoder Tutorials: Part I | Part II | Part III
- Computational Geometry in C (Joseph O'Rourke)
- Geometry Algorithms Home (Dan Sunday)
- Geometry in Action (David Eppstein)
- Computational Geometry: Algorithms and Applications (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars)
- Geometric Algorithms (Wikipedia)

Pedro Ribeiro - DCC/FCUP |
**Ăšltimo update:**