Support vector machines, convex hulls, and Gabriel graphs. You may be wondering how these concepts have anything in common with each other.

Support vector machines (SVM) are one approach to the pattern classification problem. On the other hand, convex hulls and Gabriel graphs serve as ways of representing datapoints and belong to the realm of computational geometry (more on them later).

A lot of literature has been written on the topic of support vector machines, which can often intimidate a new reader of the subject. This tutorial examines the relationship between SVMs and edited graphs (such as convex hulls and Gabriel-edited graphs) for determining an appropriate boundary for classification. It is hoped that this comparison will give the reader a better understanding of alternative techniques to solving this problem. In addition, as we will see, graph editing provides a powerful means by which the size of our dataset prior to SVM training might be reduced (which can significantly speed up this step).

The ideas presented here were inspired by a paper entitled "A Study on the Relationship Between Gabriel Graphs and Support Vector Machines" by Wan Zhang and Irwin King.

This tutorial was developed as a project for Dr. Godfried Toussaint's COMP644 Pattern Recognition course at McGill University.

As the purpose of this tutorial is to examine relationships, many details of SVM theory have been left out. A proper and thorough formalization is left to the interested reader. For further reading, several sources are cited in the References section.