TR-81: A Learning Automation Solution to the Stochastic Minimum Spanning Circle Problem

Abstract

The Minimum Spanning Circle (MSC) of N points in the plane is the smallest circle that encloses these points. This problem has been extensively studied in the literature. [1,2,4, 10, 11 ]. In this paper we consider the problem of computing the MSC of N stochastically varying points in the plane. We propose a solution to the problem which involves a heirarchy of learning automata. The automata used in this solution are the Absorbing Discretized Linear Inaction-Penalty (ADL1 p) automata which are the only known linear automata which are of an inaction-penalty flavour and yet asymptotically optimal.