Minimal enclosing circle and two and three point partitions of a plane

Partitions of a plane, based on two or three of its points, are introduced. The study of these partitions is applied to finding the minimal enclosing circle (MEC) for a set S of n planar points. MEC(S), the MEC of n points of S, is defined by either a pair of S points with the largest distance (tight two-tuple) or by a triplet of S points spread on more than half of its circumference (tight three-tuple) with the largest radius. An extension for an existing MEC by an outside point P∈S is a MEC for point P and the points of the tight tuple for the existing MEC. It has a larger radius than existing MEC. The MEC problem is dual to a problem of finding an optimal partition of S-plane by two or three points of S identified by largest circle containing these points on its circumference. A two point partition divides the S-plane in 4 regions, a three point – in 7 regions, one region is a circle in either partition. The MEC algorithm is based on this duality. It begins with a MEC of two arbitrary points of S and corresponding two point partition of S-plane. Next, each point P of S is examined in a separate step of the algorithm. If it is outside of the current MEC, its extension by this point is obtained. The tight tuple for the extension is formed by replacing either none or one or two points of current MEC’s tight tuple by point P. Which points of the tuple are to be replaced by point P depends on the region to which P belongs in a plane partition by the points of current tight tuple, consequently the tuple for the extension is made up from the basis and point P. The choice of the basis point(s) ensures that the extension contains each point of the tuple for the current MES ( present or not in the basis o