PhD Proposal: Tackling Non-locality in Computational Geometry

Exploiting property of locality is a standard practice in computational geometry. Standard tools such as Voronoi diagram, locality sensitive hashing and binary space partitioning all take advantage of locality and enable applications like nearest neighbor search and geometric minimum spanning tree. In contrast, this proposed research investigates tackling problems where locality is not immediately present or even should be actively avoided.In this talk, we first present a result of computing the Shapley values of mean width for points in 3-D, which demonstrates how a seemingly global property can be efficiently computed. Intuitively the problem computes the contribution of each individual point with respect to the average width of the point set. To solve the problem, we develop an online data structure to compute a dynamic version of discrete convolution.We then present a result of computing a maximum cardinality matching in the complement of a unit disk graph. In this problem, we actively avoid locality by not allowing matching of points that are close. We show how we can compress the graph and compute the matching on the compression. Together, we show different ways to uncover locality in the problems where locality is not obvious.Finally, we present the plan to advance the results to broader context. We propose research to show how we can apply our compression to other graph problems, especially other variants of matching problems like maximum weighted matching.Examining Committee:

Chair:Department Representative:Members:

Dr. David Mount Dr. Pratap Tokekar Dr. Aravind Srinivasan Dr. Leila De Floriani