Resource type
Thesis type
(Thesis) M.Sc.
Date created
2008
Authors/Contributors
Author: Fulek, Radoslav
Abstract
What is the smallest number tau=tau_d(n) such that for any collection C of n pairwise disjoint compact convex sets in R^d, there is a point such that any ray (half-line) emanating from it meets at most tau sets of the collection? We show an upper and several lower bounds on the value tau_d(n), and thereby we completely answer the above question for R^2, and partially for higher dimensions. We show the order of magnitude for an analog of tau_2(n) for collections of fat sets with bounded diameter. We conclude the thesis with some algorithmic solutions for finding a point p that minimizes the maximum number of sets in C we are able to intersect by a ray emanating from p in the plane, and for finding a point that basically witnesses our upper bound on tau_d(n) in any dimension. However, the latter works only for restricted sets of objects.
Document
Copyright statement
Copyright is held by the author.
Scholarly level
Language
English
Member of collection
Download file | Size |
---|---|
etd3619.pdf | 1.42 MB |