Talks

PhD Proposal: Tackling Non-locality in Computational Geometry

Shuhao Tan

5137 Brendan Iribe Center for Computer Science and Engineering (IRB)

Thursday, December 16, 2021, 10:00 am-12:00 pm

You are subscribed to this talk through .
You are watching this talk through .
You are subscribed to this talk. (unsubscribe, watch)
You are watching this talk. (unwatch, subscribe)
You are not subscribed to this talk. (watch, subscribe)

Abstract

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

Bio

Shuhao Tan is a PhD student at the University of Maryland, College Park, advised by Prof. David Mount. Shuhao's research interest focuses on geometric graph theory. More specifically, he is interested in solving flow problems and matching problems where locality is absent.

This talk is organized by Tom Hurst