5 papers
Fully Scalable MPC Algorithms for WSPD in Doubling and Euclidean Spaces
Eunjin Oh, Hyeonjun Shin
In this paper, we study the problem of constructing a -well-separated pair decomposition (WSPD) for a point set of size in the Massively Parallel Computation (…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
Seongbin Park, Eunjin Oh
In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets with , the goal is…
DAG Covers: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,…
Single-Source Shortest Path Problem in Weighted Disk Graphs
Shinwoo An, Eunjin Oh, Jie Xue
In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in t…