The points are in the euclidean plane, let $\mathbb{P}$ be the set containing all the finite sets of $\mathbb{R}^2$ points.

I am looking for a function $m : \mathbb{P} \to \mathbb{R}^+$ in order to measure misalignment :

  • If $P \in \mathbb{P}$ contains 3 aligned points then $m(P)=0$
  • If $P \in \mathbb{P}$ doesn't contain 3 aligned points then $m(P)>0$
  • $m$ continuous according to a shifting of the points (not fully defined)
  • Bonus : $m$ should be easy to compute for small inputs.

My only idea is to take the minimum of the hausdorff distance (or any other distance) between the input and any set containing 3 aligned points. But it's not easy to compute, even for small examples.


1 Answer 1


For three points $A (x_0,y_0),B(x_1,y_2), C(x_2,y_2)$ you can define $$f(A,B,C)=|\det\begin{bmatrix} 1 & 1 & 1 \\ x_0 &x_1 &x_2 \\ y_0 &y_1 &y_2 \end{bmatrix} | $$ where the outside is absolute value. Then $A,B, C$ are colinear if and only if $f(A,B,C)=0$.

Next, for all sets $P \subset \mathbb P$ of at least three points you can define $$m(P) = \min_{ \{A,B,C \} \subset P } f(,A,B,C)$$

This function satisfies the required conditions, excepting maybe the bonus. It is actually invariant under translations and rotations of the full set, and continuous with respect to small individual shifts of each point.

You have the freedom to define $m(P)$ any way you like for 1 and 2 points subsets. [you can take it constant for example].

The downside is that this function takes a lot of time to calculate.

  • $\begingroup$ Thanks ! I can use a computer to calculate the function so it's ok. $\endgroup$
    – François
    Jun 27, 2015 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .