Skip to main content

Intersecting convex sets by rays

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2008
Authors/Contributors
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.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Download file Size
etd3619.pdf 1.42 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0