Efficient packing and covering and other extremal problems in geometry

Combinatorial geometry deals with questions of enumeration and existence of geometric objects, like triangulations, sets of line segments, polytopes, packings, coverings etc. These subjects have always been the subject of investigations of classical combinatorics. In recent decades, results from combinatorial geometry have formed the bases for the design and analysis of algorithms in computational geometry. The relevance of combinatorial geometry extends to other branches of mathematics like graph theory (e.g. graph drawing), operations research (e.g. packing and covering problems).; The contributions of this dissertation fall into four categories.; In the first part, we study the fundamental problems of packing and covering: given a convex body K, find efficient arrangements of disjoint copies of K (for packing), respectively, find economical arrangements of copies of K so that their union cover the whole space (for covering). We prove certain inequalities linking the packing and covering densities of any centrally-symmetric convex disk; we also give a general upper bound for the covering density of any convex disk.; In the second part, we prove a discrepancy result in connection to simple arrangements of lines. We show that in every such arrangement there exists cells whose areas have different orders of magnitude.; The third part deals with arrangements of points, subject to various restrictions. We present a new lower bound for the number of lines containing exactly k points in a configuration of n points, no k + 1 of which are on the same line. Also, we give bounds for the maximum distance count of a planar point configuration.; Extremal graph theory proved to be one of the most useful tools in solving problems in combinatorial geometry. Recently, Linial and Rozenman considered the following problem: among all graphs on n vertices and e edges, find the ones where the sum of the square roots of the vertex degrees is minimum. They conjectured that the minimal graph is unique and consists of a maximal complete graph plus one more adjacent vertex. In the last part of this dissertation we prove this conjecture.