In machine learning applications, we often have some kind of condition defined over a set, S, of n points, which we would like to characterize—that is, “learn”— using some simple rule. For instance, these points could correspond to biological attributes of n medical patients and the condition could be whether a given patient tests positive for a given disease or not, and we would like to learn the correlation between these attributes and this disease. Think of the points with positive tests as painted “red,” and the tests with negative tests as painted “blue.” Suppose that we have a simple two-factor set of attributes; hence, we can view each patient as a two-dimensional point in the plane, which is colored as either red or blue. An ideal characterization, from a machine learning perspective, is if we can separate the points of S by a line, L, such that all the points on one side of L are red and all the points on the other side of L are blue. So suppose you are given a set, S, of n red and blue points in the plane. Describe an efficient algorithm for determining whether there is a line, L, that separates the red and blue points in S. What is the running time of your algorithm?