In this thesis we consider extensions and generalizations of some classical problems
in Combinatorial Geometry. Our work is an offshoot of four classical problems in
Combinatorial Geometry. A fundamental assumption in these problems is that the
underlying point set is R2. Two fundamental themes entwining the problems considered
in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since.
Avis et al. in 2001 posed the following question which we call the n-interior point
problem: Is there a finite integer g(n) for every n, such that, every point set P with
g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset
which is a convex polygon that contains exactly n interior points. They showed that
g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers.
We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily
C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed
the following fundamental question which can be considered as a generalised version of
Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known.
Inspired by the original question of Danzer and Gr¨unbaum we consider their question
in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting.
In the third part of this thesis, we broadly look at hitting and covering questions
with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively.
These problems has been well studied in the case when P = R2. We systematically
look at the case when P is finite, showing bounds for intervals, halfspaces, orthants,
unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2.
Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the
strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any
object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express
the bound on the size of the set Q in terms of ǫ.
Let G be a uniform √n × √n grid. It is an intriguing question as to whether we
get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.
| Identifer | oai:union.ndltd.org:IISc/oai:etd.ncsi.iisc.ernet.in:2005/3134 |
| Date | January 2014 |
| Creators | Bharadwaj, Subramanya B V |
| Contributors | Govindarajan, Sathish |
| Source Sets | India Institute of Science |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Relation | G26945 |
Page generated in 0.0027 seconds