M.Sc Thesis | |

M.Sc Student | Buzaglo Sarit |
---|---|

Subject | The VC-Dimension of s-Intersecting Curves |

Department | Department of Mathematics |

Supervisor | PROF. Rom Pinchasi |

Full Thesis text |

We present a collection of results in Combinatorial Geometry, aggregated in three chapters. The first one deals with the VC-dimension of a family of subsets of points in the plane, surrounded by simple closed curves. The second deals with sweeping of an arrangement of curves. The last chapter deals with polygonal paths with no small angles.

Given a set
X, a set-system on the ground set X is a collection of subsets of X. The
Vapnik-Chervonenkis dimension, or VC-dimension for short, is a parameter
assigned to a set system. An important result related to the VC-dimension is
the Shatter-Function-Lemma, which asserts that a set system F on a finite
ground set X and with VC-dimension d consists of O(|X|^{d}) members. We
consider a set P of n points in the plane and a collection C of simple closed
curves, each of which avoids the points of P. We show that if C satisfies two
properties, namely the connected intersection property and the s-intersecting
property, then the set system F, which consists of all the subsets of P that
are surrounded by curves in C, has VC dimension at most s. By the
Shatter-Function-Lemma, F consists of O(n^{s}) members.

The second problem we consider deals with sweeping by a ray of an arrangement of curves in the plane. J. Snoeyink and J. Hershberger proved that any collection of pseudo circles surrounding a common point can be swept by a ray. We have generalized this result for a collection of simple closed curves all surrounding a common point, and which satisfy the connected intersection property.

The last chapter deals with a special case of a problem of S.Fekete and G.J Woeginger. Given a finite set X of points in the plane, and α>0, is it possible to find a polygonal path P, whose vertices are the points in X, such that the angles between every two consecutive edges of P are at least α? Fekete and Woeginger conjectured that it is possible for α≤π/6. We show that if the points are in convex position, then for every α≤π/5, there exists a path on the points with no angle smaller than α, and that this upper bound on α is the best possible.