SEPARATING COLLECTIONS OF POINTS IN EUCLIDEAN SPACES

Given two disjoint convex sets A and B in E(d), a hyperplane h in E(d) separates them if A lies on one of the half spaces defined by h while B lies on the complementary half space. Given a collection F of conve x sets in Ed We say F is separated by a set of hyperplanes H if every pair of elements of F is separated by some hyperplane of H. We deal he re with the case that the convex sets are all points. Let f(n, d) be t he minimum number of hyperplanes always sufficient and occasionally ne cessary to separate n points in general position in E(d). We prove tha t [(n - 1)/d]less than or equal to f(n, d)less than or equal to[(n - 2 ([log(d)]))/d] + [log(d)]. When d is even the lower bound can be impro ved to [n/d]. In the planar case this gives us f(n, 2) = [n/2]. We pro ve the upper bound by presenting an algorithm that generates a separat ing family of hyperplanes H that satisfies the upper bound. In dimensi on 2 the algorithm has a time complexity of O(n log(n)). Finally, we s how that in the planar case H can be stored such that retrieving a lin e in H that separates a given pair of points from P can be found in O( 1) expected time and worst-case time of O(log(2)(n)).