Ph.D Thesis
Ph.D Student Itay Ben-Dan Topics in Combinatorial Geometry and Combinatorics Department of Mathematics Full Professor Pinchasi Rom

Abstract

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 Xk;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 Xk;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 l1 and l2, 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 l1 and l2, 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 l1 and l2, 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 l1 and l2, 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)> cP for every set P in general position in the plane and some absolute constant c that is strictly greater than 1/8.