Given two point sets, $B$ consisting of blue points, and $R$ of red points, on the plane.

The problem is to formulate a theoretical model to compare the average runtime of the Computational Geometric (CG) Algorithm and the Perceptron Learning (PL) for shattering two sets of points by a line. ( Briefly, CG tests if there exists a line, $ax+by = c$ such that the system of equations $ax_r+by_r\leq c; ax_b+by_b \geq c$ for all $(x_b,y_b) \in B$ and $(x_r,y_r) \in R$ is consistent; if so, it finds one such.) AFAIK, only empirical models are known thus far, where we take a large number of such point sets and test out the performance of CG and PL.

While I can't see any clear solution to this, I am looking for one along the following lines: Choose 2 random integers, $b$ and $r$ in the range $[1,n]$ where $n$ is a large integer, to appear in the answer as a parameter. Choose $b$ blue points and $r$ red points within the unit square. Compute the average runtime performance of CG (essentially determining the complexity of determining consistency of linear equations on a random set of values) and PL (essentially determining the number of weight changes on a random data set) by a multi-fold integration. Further, average across all possible choices of $b$ and $r$ in the range $[1,n]$.

Can you offer more insight or a better formulation?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.