Ph.D Thesis | |

Ph.D Student | Ben-Dan Itay |
---|---|

Subject | Topics in Combinatorial Geometry and Combinatorics |

Department | Department of Mathematics |

Supervisor | PROF. Rom Pinchasi |

Full Thesis text |

In this work we present a collection of results in
combinatorial geometry aggregated in four chapters. The firrst one deals with
continuous motion of points in the plane and its relations to bounding the
numbers of convex polygons with empty interior. Let *P *be a set
of *n *points in general position in the plane.

Let *X**k;j*(*P*) denote the number of convex *k*-gons
determined by *P *with exactly *j
*points of *P *in
their interior. We derive, using elementary proof techniques, several
equalities an inequalities involving the quantities *X**k;j*(*P*) and
several related quantities. Some of this relationship are also extended to
higher dimensions. We present several implications of these relationships, and
discuss their connections with several open problems.

In the second chapter we prove that for any *b > *0
there exists an angle *f*= *f*(*b*) between 0 and *pi*, depending only on *b*, with
the following two properties: (1) For any continuous probability measure in the
plane one can find two lines *l*1 and *l*2,
crossing at an angle of (at least) *f(b)*, such that the measure of each of the two opposite
quadrants of angle *pi-f(b),* determined by *l*1 and *l*2,
is at least *1/2-b*. (2) For any set *P *of *n *points
in general position in the plane one can find two lines *l*1 and *l*2, crossing at an angle of (at
least) *f(b) *and moreover at a point of *P*, such
that in each of the two opposite quadrants of angle *pi-f(b),* determined
by *l*1 and *l*2,
there are at least (*1/2-b*)*n * points of *P
*for n>100.

In the third chapter we make an attempt to
characterize all the pairs (*a,b*) s.t. there always exists a point *z *in the
plane and two opposite quadrants determined by axis
parallel lines through *z *s.t. one contains at least *an *points
of *P *and the other contains at least *bn *points
of *P*.

In the fourth chapter we deal with the following
question: For every *x **in **P *let *D*(*x; P*) be the maximum number such that there are at least *D*(*x; P*)
points of *P *in each of two opposite quadrants determined among
all two perpendicular lines through *x*. Define *D*(*P*) = max*(x **in **P) **D*(*x; P*). We
show that *D*(*P*)> c*P** *for
every set *P *in general position in the plane and some absolute
constant *c *that is strictly greater than 1/8.