Theory of Computation - Publications

Authors are listed in alphabetical order in most of our publications as per tradition in Theoretical Computer Science.

Shinwoo An and Eunjin Oh, ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs. (SoCG 2024)
Kyungjin Cho,Eunjin Oh, Haitao Wang, and Jie Xue, Optimal Algorithm for the Planar Two-Center Problem. (SoCG 2024)
Kyungjin Cho, Jihun Shin, and Eunjin Oh, Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners. (AAAI 2024)
Eunjin Oh and Seungyeok Oh, Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs (ESA 2023)
Shinwoo An, Kyungjin Cho, and Eunjin Oh, Faster Algorithms for Cycle Hitting Problems on Disk Graphs (WADS 2023)
Kyungjin Cho, Eunjin Oh, and Seunghyeok Oh Parameterized Algorithms for Planar Disjoint Paths: Exponential in k^2 and Linear in n (SODA 2023)
Kyungjin Cho and Eunjin Oh, Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces (ISAAC 2021)
Shinwoo An and Eunjin Oh, Feedback Vertex Set in Unit Disk Graphs. (ISAAC 2021)
Shinwoo An and Eunjin Oh, Reachability Oracles in Geometric Transmission Graphs. (WADS 2021)
Eunjin Oh, Shortest Path Queries in Geometric Networks. (ISAAC 2020)
Eunjin Oh, Optimal Algorithm for Geodesic Nearest-Point Voronoi Diagrams. (SODA 2019)

Eunjin Oh Point Location in Incremental Planar Subdivisions. (ISAAC 2018)
Eunjin Oh Minimizing Distance-to-Sight in Polygonal Domains. (ISAAC 2018)
Eunjin Oh and Hee-Kap Ahn, Approximate range clustering queries. (SoCG 2018)
Eunjin Oh and Hee-Kap Ahn, Point location in dynamic planar subdivisions. (SoCG 2018)
Eunjin Oh and Hee-Kap Ahn, Finding Pairwise Intersections of Rectangles in a Query Rectangle. (ISAAC 2017)
Eunjin Oh and Hee-Kap Ahn, Time-Space Trade-offs for Shortest Paths and Shortest Path Trees in a Simple Polygon. (ISAAC 2017)
Eunjin Oh and Hee-Kap Ahn, Dynamic geodesic convex hulls in dynamic simple polygons. (SoCG 2017)
Eunjin Oh and Hee-Kap Ahn, Voronoi diagrams for a moderate-sized point-set in a simple polygon. (SoCG 2017)
Eunjin Oh and Hee-Kap Ahn. Assigning weights to minimize the covering radius in the plane. (ISAAC 2016)
Eunjin Oh and Hee-Kap Ahn. A near-optimal algorithm for finding an optimal shortcut of a tree. (ISAAC 2016)
Eunjin Oh, Luis Barba, and Hee-Kap Ahn, The farthest-point geodesic Voronoi diagram for points on the boundary of a simple polygon. (SoCG 2016)
Eunjin Oh, Jean-Lou De Carufel, and Hee-Kap Ahn, The 2-center problem in a simple polgon. (ISAAC 2016)

Kyungjin Cho and Eunjin Oh, Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces. CGTA (invited), 2023
Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn, Eunjin Oh, and Micha Sharir, The Maximum-Level Vertex in an Arrangement of Lines. Discrete & Computational Geometry, 2022
Shinwoo An and Eunjin Oh, Reachability Oracles in Geometric Tranmission Graphs. Algorithmica, 2022
Eunjin Oh, Luis Barba, and Hee-Kap Ahn, The farthest-point geodesic Voronoi diagram for points on the boundary of a simple polygon. Algorithmica, 2020
Eunjin Oh and Hee-Kap Ahn, Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discrete & Computational Geometry, 2020
Eunjin Oh and Hee-Kap Ahn, A new Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms Algorithmica, 2020