1 of 8

ICPC SWERC Training

Session 7: Geometry

2 of 8

Representing 2D points?

Attention!

Returns type T

Question 1. Define dot and cross with complex numbers?

3 of 8

Primitives in 2D geometry

Read chapter 2 of:

https://victorlecomte.com/cp-geo.pdf

4 of 8

Sweep line algorithms

Is there an intersection between segments?

Which are the two closest points?

5 of 8

Convex hull algorithms

Graham scan

Andrew's monotone chain algorithm

6 of 8

Quizz

Question 2. How to compute:

  • triangle with smallest perimeter?
  • triangle with largest area?
  • triangle with smallest area?
  • triangle with largest perimeter?

7 of 8

Operation on (convex) polygons

  • Translation
  • Rotation
  • Intersection
  • Union
  • Minkowski sum

8 of 8

Advanced topic: Voronoi and Delaunay

Voronoi diagram (in red): the Voronoi cell of a seed s is the polygon containing all points which are closer to s than to any other seed.

​

Delaunay triangulation (black edges): a Delaunay triangle is such that its circumcircle does not contain any seed.

Given a set of (black) points, called seeds, we define the Voronoi diagram and Delaunay triangulation.

​