4

Sorry if this has been asked/answered but I couldn't find anything here or on Google, and for sorry for the poor wording of the title. Anyway, here's my question:

Given a set of points in $\mathbb{R}^2$, find the equation of a line such that half of the points on the plane lie on one side of the line, and half lie on the other side. If there are an odd number of points the line must go through one of the points, as well as split the remaining points in half. The odd number of points case is the only one in which our line may pass through a point.

For example, if we have a single point, the line simply goes through that point. If we have $2$ points, say on $(0,0)$ and $(0,2)$, the line might be defined by $y=1$ (though something like $y=2x+1$ would also work. For the purposes of this problem the line $x=0$ would not work). If we have $4$ points, $(0,1), (-1,0), (0,-1)$, and $(1,0)$, then the equation $y=x$ works.

A fairly naive solution would be to always return a line with the equation $y = c$, where $c$ is the median $y$ value of all of our points. This approach works on sets of points such that the median y value is unique, but not otherwise (as our line will now pass through more than a single point.).

How might I go about finding a general solution to this problem?

yoknapatawpha
  • 4,009
dashiell
  • 143

1 Answers1

3

I assume the set of points is finite. Otherwise your question is meaningless.

There are then finitely many slopes for the lines between two points in the set. Choose any real number $m$ that is not one of those slopes.

The values of $y_i-mx_i$ will then be distinct for each point. Let the median value of those be $b$. Your desired line is then $y=mx+b$.

There are several practical ways to choose the slope $m$. You could try zero (your naïve approach) and see if the median is unique. If not try $1$, then $1/2$, then $1/3$, etc. There are, of course, yet other ways.

Rory Daulton
  • 32,288