| In this thesis we investigate several problems in combinatorial geometry. Some of them have algorithmic applications.;Related to a question of Erdo&huml;s about the existence of any fixed size empty polygon in arbitrarily large sets of points, we construct point sets which have a small number of empty convex polygons. This improves on some earlier results of Barany, Furedi and Valtr.;Answering a question of Aharoni and Saks, we prove that given a two colored set of points in the plane, there exists a non-crossing matching of the points, using straight line segments, in pairs having the same color, which matches at least 83.33% of the points. An O(n log n) algorithm which achieves this guarantee is derived. On the other hand, there exist configurations of points such that any matching with the above properties matches at most 99.36% of the points.;A Ramsey-type problem is the study the size of the largest clique or independent set in special classes of graphs. We obtain such bounds for unions of comparability graphs and for unions of perfect graphs. A similar problem is the study of the size of the largest pairwise intersecting or pairwise disjoint subfamily of a family of convex compact sets in the plane. We show that the best known upper bound construction for this problem can be achieved using sets in a restricted position.;We investigate space-time trade-offs for two ranking and searching queries: in the first, given a set of lines in general position in the plane, and a query vertical line, count the number of intersection points of pairs of lines which lie in the left half-plane bounded by the line; in the second, given two sets of numbers of the same cardinality, find the number of sums of the Cartesian sum which are less than the query value.;We refine the analysis of a lower bound construction of a point set having many non-crossing spanning trees. We also give more precise upper bounds on the maximum number of non-crossing spanning trees, perfect matchings and simple polygons of a planar point set.;We consider the d-interval problem, for which we generalize a lower bound construction. This problem is concerned with the relation between the covering number and the matching number of the underlying hyper-graph. |
