In this talk, I will talk about my recent work on MPC algorithm for constructing a $(1/varepsilon)$-emph{well-separated pair decomposition} (WSPD). In particular, we focus on the emph{fully scalable regime} where each machine has local memory of size $O(n^delta)$ for an arbitrary constant $delta in (0,1)$. The WSPD is a fundamental tool in computational geometry with numerous applications. However, to the best of our knowledge, even in Euclidean space, no MPC algorithm is known to compute a WSPD in $o(log n)$ rounds. The only known approach simulates the classic PRAM algorithm of Callahan and Kosaraju, which requires $O(log n)$ rounds in the MPC model. In this talk, I will present $O(1)$-round MPC algorithm for constructing a $(1/eps)$-WSPD of size $(1/varepsilon)^{O(d)} n$ for point sets in a doubling metric space. Moreover, we demonstrate several applications of our WSPD construction: computing a $(1+varepsilon)$-spanner, a $(1-varepsilon)$-approximation diameter, the closest pair, and the $k$-nearest neighbors ($k$-NN). While our $k$-NN algorithm is specific to Euclidean space, the other three problems can be solved in both Euclidean and doubling metric spaces

Eunjin Oh is an associate professor at POSTECH. Before joining POSTECH, she was a postdoctoral researcher at the Max Planck Institute for Informatics. She received her Ph.D. from POSTECH in 2018. Her research focuses on geometric optimization, including geometric matching and geometric network design.