Complexity of perceptron recognition for a class of geometric patterns

In this paper, we study the recognition complexity of discrete geometric figures (rectangles, squares, circles, ellipses) on a retina by diameter-limited and order-restricted perceptrons. We construct a diameter-limited recognition perceptron for the family of rectangles, beginning with local configurations, which is different from the one shown by Minsky et al. (Perceptrons: An Introduction to Computational Geometry, extended edition, MIT Press, Cambridge, MA, 1988). In addition, we demonstrate the nonexistence of diameter-limited recognition perceptrons for squares, circles and ellipses. Finally, for squares and ellipses we construct an order-restricted perceptron with constant coefficients, using an original technique which decomposes the characterization of the figures into local and global features.