Prove that out of $2n+3$ points on a plane we can construct a segment using two points A, B such that the rest of $2n+1$ points lie on the same side of segment AB. It is given that no three points are collinear and no four points are con-cyclic.
I was trying to work through this by taking any two points, say $P$ and $Q$. First we take the side of $PQ$ where less number of points are present, and join $P$ to a point $T$ which lies on this side of less points and keep repeating this process.
Initial thought would be that now even lesser points will lie on a side of $PT$, but the problem is this isn't true when some points lie between $QP$ extended and $TP$ extended(like Point $N$). Beyond this, I am unable to find some way.
$P, Q, T, N$ and other arbitrary points" />
Imagine the smallest envelop covering all of your points. It is a polygon connecting the outermost points of the set. This is called the convex hull of your point set. The convex hull divides the point set into two separate subsets: points that are on it, and points that are in it. For example, in the figure that you posted, point $P$ is in the convex hull, whereas point $J$ is on the convex hull.
It seems that your suggested approach has the problem that you identified because you start drawing lines from point $P$ in the convex hull. On the contrary, if you start from a point on the convex hull, this problem will be resolved.
Now, all we need to do is find a point on the convex hull. One easy way is to sort the points by their vertical (or horizontal) coordinates, and pick the point with the smallest (or largest) value. That point is surely on the convex hull. (Note that if there are two points with this value for the selected coordinate, then the line connecting those two points is the line you are looking for, and your algorithm ends here. Note also that because of the constraint of collinearity there won't be three or more points with the same value for the selected coordinate.) In your figure, for example, the point with the lowest value of vertical coordinate is $J$.
If you are interested in this subject subject you can find good reads under the name of computational geometry.