Size of Connex Components in unoriented 2D graph | Ensimag's Project

The project

• Considering a set of points $p_i$, $1 \le i \le n$, and a limit distance $s$, we want to know the number a connex component of the given set of points and distance.
  Two vertices $p_i$ and $p_j$ are linked by an edge if $d(p_i, p_j) \le s$.
• A connex component is a sub-graph where all the vertices are linked by transitivity.

A solution

I worked in pair with Hugo on different methods. We studied quadtrees, M-trees, VP-trees, Divide-and-conquer algorithm, optimization …
Details of our work are available here (in french):