演讲人： Haitao Wang University of Utah
时间： 2024-06-19 16:00-2024-06-19 17:00
地点：FIT 1-222
内容：

In this talk, I will present our recent results on the shortest path problem in unit-disk graphs. For a set P of n points in the plane, its unit-disk graph G(P) is a graph whose vertex set is P, such that two points of P have an edge if their (Euclidean) distance is at most 1, and the weight of the edge is equal to the distance between the two points. Given P and a source point s in P, the shortest path problem is to compute shortest paths from s to all points of P in G(P). Since G(P) may contain \Omega(n^2) edges in the worst case, it would take \Omega(n^2) time to solve the problem if G(P) is constructed explicitly. In this talk, I will present a near-linear time algorithm for the problem without constructing the graph explicitly, which is achieved by utilizing certain geometric information. More specifically, the runtime of the algorithm is O(n log^2 n / loglog n). We also show that the problem can be solved in O(n log n) time under the algebraic decision tree model (in which only comparisons are counted toward the time complexity), matching an \Omega(n log n) lower bound under the same model. In addition, I will briefly discuss a reverse shortest path problem in unit-disk graphs and propose several open problems. 

个人简介:

Haitao Wang is an Associate Professor in Kahlert School of Computing at the University of Utah. He obtained a Ph.D. degree in Computer Science from the University of Notre Dame. His research interests are mainly in computational geometry, algorithms, and theoretical computer science.