I just started reading Computational Geometry book and it presents the following algorithm
and states that we check $n^2 - n$ pairs of points. I do not understand why and how... If I have 3 points 1,2,3 then I would check (1,2) (2,3) (3,1) right? Not 9 - 3 = 6 pairs...
On
The algorithm considers all ordered pairs $(p,q)$ for distinct $p$ and $q$. The set of ordered pairs is the Cartesian product $P \times P$.
In your example, where $P=\{1,2,3\}$, the complete set of ordered pairs is $\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$, counting $3^2$ elements.
Because the algorithm ignores $(1,1)$, $(2,2)$ and $(3,3)$, you can subtract $3$ from the number of pairs considered.
That makes $n^2-n$ pairs, which is 6 in your example.
Should the order matter? It appears to be discussing ordered pairs, so $(1,2)$ and $(2,1)$ are distinct. In general, if order doesn't matter, we can take $\binom{n}{2} = (n^2-n)/2$ pairs, but if order does matter, then we need to multiply by the number of permutations for a pair, which means we must take $2!\binom{n}{2} = n^2-n$ points.
If we generalize to $k$-tuplets, then we can take $\binom{n}{k}$ and $k!\binom{n}{k}$ respectively. These are the fomulae for combination and permutation.