Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Abstract

The method of constructing convex linear hulls of a finite set of points is often used in recognition problems. In an \(n\)-dimensional space, \(n\)-element subsets of points are considered for this purpose. If the remaining points lie on the same side of the hyperplane containing the selected points, then this hyperplane is called a face. Checking whether a new point belongs to the convex linear hull is reduced to verifying a system of linear inequalities determined by the faces.

We propose considering a coarse-grained problem in which the coordinates of the points take three values, \(0,1,-1\), interpreted as elements of a field with three elements. In this setting, the linear form is equal to zero at points lying on the hyperplane, equal to \(1\) on one side of it, and equal to \(-1\) on the other side. Checking whether a point belongs to the convex linear hull is reduced to verifying the conditions \(S_a(x)\in \{0,\lambda _a\}\) for all faces \(S_a\) of the convex linear hull, where the value \(0\) corresponds to the point lying on the hyperplane \(S_a\), while \(\lambda _a\) is the common value of the linear form at the points of the set that do not belong to \(S_a\). Thus, whether a new point belongs to the convex linear hull is determined by its position relative to all faces of the hull.

Keywords: convex linear hull, finite fields, $E_3^n$ space, linear forms, pattern recognition, image classification.