Abstract:

The study of algorithms under imprecise input can help us to construct algorithms that are guaranteed to be correct and efficient even if the input is imprecise, for example, the real position of each data point is not more than $\epsilon$ distance away from its given position.

In this talk, I will review several papers related to geometric algorithms on imprecise data, including computing the convex hull, diameter of imprecise data. I will also talk the the \emph{metric violation distance} problem: given a set of pairwise distances, modify the minimum number of distances such that the resulting set forms a metric, which will appear on SODA 2018.

Biography:

Chenglin Fan，2011年计算机专业硕士毕业于中南大学，2011-2014任深圳先进技术研究院数据挖掘工程师，现为美国得克萨斯达拉斯分校计算机专业在读博士，研究方向计算几何，近似算法。