## Hitting Geometric Range Spaces using a Few Points

dc.contributor.advisor | Govindarajan, Sathish | |

dc.contributor.author | Ashok, Pradeesha | |

dc.date.accessioned | 2018-02-14T22:09:16Z | |

dc.date.accessioned | 2018-07-31T04:38:52Z | |

dc.date.available | 2018-02-14T22:09:16Z | |

dc.date.available | 2018-07-31T04:38:52Z | |

dc.date.issued | 2018-02-15 | |

dc.date.submitted | 2014 | |

dc.identifier.uri | http://etd.iisc.ac.in/handle/2005/3115 | |

dc.identifier.abstract | http://etd.iisc.ac.in/static/etd/abstracts/3975/G26352-Abs.pdf | en_US |

dc.description.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 deﬁned by the intersection of geometric objects with P . The algorithmic question of ﬁnding the minimum-sized hitting set for a given range space is well studied and is NP-Complete even for geometric range spaces deﬁned 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 ﬁnd 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 speciﬁc geometric range spaces where the size of the hitting set is ﬁxed as a small constant. We study the small hitting set problem mainly for two broad classes of range spaces. We ﬁrst consider the Dense range space (P, S) where P is a set of n points in Rd and S is deﬁned by “dense” geometric objects i.e, geometric objects that contain more than a constant fraction, say �, of points from P . We ﬁx 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 deﬁned 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 deﬁned 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 deﬁned by a ﬁxed 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 ﬁrst selection lemma for induced rectangles, induced special rectangles and induced disks. We prove an exact result for the strong variant of the ﬁrst selection lemma for axis-parallel rectangles. We also prove exact results for the strong variant of the ﬁrst selection lemma for some subclasses of axis-parallel rectangles like orthants and slabs. We prove strong ﬁrst selection lemma with almost tight bounds for skylines, another sub-class of axis-parallel rectangles. We prove bounds for ﬁrst 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. | en_US |

dc.language.iso | en_US | en_US |

dc.relation.ispartofseries | G26352 | en_US |

dc.subject | Algorithms - Geometric Range | en_US |

dc.subject | Induced Range Space | en_US |

dc.subject | Dense Range Space | en_US |

dc.subject | Computational Geometry | en_US |

dc.subject | Strong Centerpoints | en_US |

dc.subject | Lemmas | en_US |

dc.subject | Geometric Objects | en_US |

dc.subject | Hyperplanes | en_US |

dc.subject | Convex Polytopes | en_US |

dc.subject.classification | Mathematics | en_US |

dc.title | Hitting Geometric Range Spaces using a Few Points | en_US |

dc.type | Thesis | en_US |

dc.degree.name | PhD | en_US |

dc.degree.level | Doctoral | en_US |

dc.degree.discipline | Faculty of Engineering | en_US |