Hitting Geometric Range Spaces using a Few Points

Abstract

A range space (P, S) consists of a set P of n elements and a collection S = {S1,...,Sm} of subsets of P , referred to as ranges. A hitting set for this range space refers to a subset H of P such that every Si in S contains at least one element of H. The hitting set problem is studied for many geometric range spaces where P is a set of n points in Rd and the ranges are defined by the intersection of geometric objects with P . The algorithmic question of finding the minimum-sized hitting set for a given range space is well studied and is NP-Complete even for geometric range spaces defined by unit disks. The dual of the hitting set problem is the equally well studied set cover problem. A set cover is a sub-collection C⊆S such that every element in P is contained in at least one range in C. A classic problem which is related to the minimum set cover problem is the maximum coverage problem. In this problem, given a range space (P, S) and an integer k, we have to find k ranges from S such that the number of elements in P that are covered by these k ranges are maximized. In this thesis, we study combinatorial questions on a similar variant of hitting set problem for specific geometric range spaces where the size of the hitting set is fixed as a small constant. We study the small hitting set problem mainly for two broad classes of range spaces. We first consider the Dense range space (P, S) where P is a set of n points in Rd and S is defined by “dense” geometric objects i.e, geometric objects that contain more than a constant fraction, say �, of points from P . We fix the size of the hitting set as a small constant k and investigate bounds on the value of � such that all ranges that contain more than �n points from P are hit. Next we consider the Induced range space (P, I) where P isa setof n points in R2 and the ranges are all geometric objects that are induced(spanned) by P i.e., the ranges are defined by geometric objects that have a distinct tuple of points from P on its boundary. For Induced range spaces, we prove bounds on the maximum number of ranges that can be hit using a single point. We also prove combinatorial bounds on the size of the hitting set for various families of induced objects. Now, we describe the problems that we study in this thesis and summarize the results obtained. 1. Strong centerpoints: Here we study the small hitting set question for dense range spaces when the size of hitting set is one. This is related to a classic result in geometry called Centerpoint Theorem. A point x ∈ Rd is said to be the centerpoint of P if x is contained in all convex objects that contain more than dn points from P . Centerpoint Theorem states d+1 that a centerpoint always exists for any point set P . A centerpoint need not be an input point. A natural question to ask is the following: Does there exist a strong centerpoint? i.e., is it true that for any given point set P there exists a point p ∈ P such that p is contained in every convex object that contains more than a constant fraction, say �, of points of P ? It can be easily seen that a strong centerpoint does not exist even for geometric range spaces defined by half spaces. We study the existence and the corresponding bounds for strong centerpoints for some range spaces. In particular, we prove the existence of strong centerpoint and show tight bounds for the following range spaces. Convex polytopes defined by a fixed set of orientations : Geometric range spaces like those induced by axis-parallel boxes, skylines and downward facing equilateral triangles belong to this family of convex polytopes. Hyperplanes in Rd Range spaces with discrete intersection 2. Small Strong Epsilon Nets: This can be considered as an extension of strong centerpoints. This question is related to a well studied area called �-nets. N ⊂ P is called a (strong) �-net of P with respect to S if N ∩ S =�∅ for all objects S ∈S that contain more than �n points of P . We study the following question. Let �S∈ [0, 1] represent the smallest real number such that, for any given point set P , there exists Q ⊂ P of size i which is an �S-net with respect to S. Thus a strong centerpoint will be an �S1 -net. We prove bounds on �Si for small values of i where S is the family of axis-parallel rectangles, halfspaces and disks. 3. Strong First Selection Lemma: Here we consider the hitting question for induced range spaces when the size of the hitting set is one. In other words, given an induced range space, we prove bounds on the maximum number of ranges that can be hit using a single input point. Such questions are referred to as First Selection Lemma and are well studied. We consider the strong version of the First Selection Lemma where the “heavily covered” point is required to be an input point. We study the strong first selection lemma for induced rectangles, induced special rectangles and induced disks. We prove an exact result for the strong variant of the first selection lemma for axis-parallel rectangles. We also prove exact results for the strong variant of the first selection lemma for some subclasses of axis-parallel rectangles like orthants and slabs. We prove strong first selection lemma with almost tight bounds for skylines, another sub-class of axis-parallel rectangles. We prove bounds for first selection lemma for disks in the plane and exact results for a special case when the discs are induced by a centrally symmetric point set. 2 Hitting all Induced Objects: Here we discuss and prove combinatorial bounds on the size of the minimum hitting set for induced range spaces. We prove tight bounds on the hitting set size when induced objects are special rectangles, disks and downward facing equilateral triangles.