2025/26 eat & LEARN Seminar Series (5)

• Title: MPC Algorithms for Geometric Proximity Problems
• Speaker: Prof. Eunjin Oh (Department of Computer Science and Engineering, POSTECH)
• Venue: Room #302, Science Bldg. IV, POSTECH
• Time: 6:00 PM - 8:00 PM, February 6, 2026

Video

Abstract

In this talk, I will talk about my recent work on MPC algorithm for constructing a (1/ε)-well-separated pair decomposition (WSPD). In particular, we focus on the fully scalable regime where each machine has local memory of size O(n^δ) for an arbitrary constant δ ∈ (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/ε)-WSPD of size (1/ε)^{O(d)}n for point sets in a doubling metric space.

Moreover, we demonstrate several applications of our WSPD construction: computing a (1+ε)-spanner, a (1-ε)-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.

Photos from Seminar