Hire an Illini
Mitchell Francis Jones
- Advisor:
- Sariel Har-Peled
- Departments:
- Areas of Expertise:
- Randomized & approximation algorithms
- Computational geometry
- Theoretical computer science
- Thesis Title:
- On the Search for Geometric Orders, Centers, and Separation
- Thesis abstract:
- Over the previous decade, there has been an explosion in the amount of data that needs to be stored, processed, and queried efficiently. Arguably, this is due to the large improvements in data collection methods and machine learning algorithms. A large portion of the data is naturally geometric, consisting of point sets or other simple geometric objects. Examples of operations one may want to perform on finite point sets include ordering the points for storage, sorting, and searching, computing statistical summaries of the points, or breaking the pointers into smaller clusters to be further processed in parallel. In this thesis, we study a variety of problems related to geometric orders, centers, and separation from a theoretical perspective. In part one, we study a new type of geometric ordering known as locality-sensitive orderings. Given a finite point set $P \subseteq [0,1)^d$, we describe a collection of orderings (embeddings of $P$ onto an interval on the real line) which have the property that for any two points in $p, q \in [0,1)^d$, there is an ordering in which all points between $p$ and $q$ according to the ordering are "close" to either $p$ or $q$ in the original space. Locality-sensitive orderings leads to surprisingly simple data structures for a variety of low-dimensional approximate proximity based problems in computational geometry. In the second part of this thesis, we examine various ways to define the center of a point set, and develop efficient algorithms for computing such summaries in the process. We begin by developing a new randomized algorithm for computing the approximate centerpoint of a point set. Next, we develop new exact algorithms for finding the yolk of a point set, whose motivation and definition rises from ideas in voting theory. We also explore the connection between centerpoints and weak $\eps$-nets by presenting some new alternatives to weak $\eps$-nets. Finally, we investigate how the notion of separation in computational geometry can be utilized. In particular, we develop a new approximation algorithm for computing the minimum number of lines needed to separate all pairs of a given planar point set. Afterwards, we study the problem of active-learning a concept class which is a convex body. We develop new learning algorithms which assume the computational model has access to an efficient separation oracle for the given convex body.
- Downloads:
Contact information:
mfjones2@illinois.edu