Data Structures for Point Enclosing Problems on the Circle and the Square

Abstract

A well-studied class of geometrical problems is the class of point enclosing problems. Here we are given a point set P and a convex shape s. Either we have to enclose as many points of P with s or we have to enclose a certain number of points and we minimise the size of s. In both cases the input consists of a set points and value which is either the number of points k that we must enclose or the size r of the shape. We consider specifically the interval for 1-dimensional points and the circle and square for 2-dimensional points. Although these problems have been studied extensively in the last few decades, we take a different approach. Instead of solving one of these problems directly, we construct, for a specific problem, a data structure on the point set such that we can query either a value k or r (depending on the problem) and answer the problem more quickly. Building the data structure might take more time than computing the problem directly, but if we need to solve the same problem for different values of k or r, this approach can be faster than solving the problem from start for each individual input.