On the search for geometric orders, centers, and separation

Jones, Mitchell Francis

Permalink

https://hdl.handle.net/2142/113010 Copy

Description

Title

On the search for geometric orders, centers, and separation

Author(s)

Jones, Mitchell Francis

Issue Date

2021-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Har-Peled, Sariel

Doctoral Committee Chair(s)

Har-Peled, Sariel

Committee Member(s)

• Chan, Timothy
• Chekuri, Chandra
• Varadarajan, Kasturi

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• theoretical computer science
• computational geometry
• approximation algorithms
• randomized algorithms
• centerpoint
• order
• separation
• yolk
• active learning

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 points into smaller clusters for further processing. In this thesis, we study many of the aforementioned problems from a theoretical perspective. In part one we develop a new technique called locality-sensitive orderings. Given a finite point set P in [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 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 these centers in the process. We develop 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 explore the connection between centerpoints and weak eps-nets by presenting some new alternatives to weak eps-nets. In the third part, we investigate the notion of separation in computational geometry. 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."

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/113010

Copyright and License Information

Copyright 2021 Mitchell Jones

Owning Collections