Theory of Computation - Publications

Theory of Computation

Publications

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

Conference Papers (2019-Current)

Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff, Range Counting Oracles for Geometric Problems. (SoCG 2025)
Shinwoo An, Eunjin Oh, and Jie Xue, Single-Source Shortest Path Problem in Weighted Disk Graphs. (SoCG 2025)
Shinwoo An, Eunjin Oh, and Jie Xue, Approximation Algorithms for Geometric Multimatching Problem. (STOC 2025)
Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee, Eunjin Oh, and Hyeonjun Shin,
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs. (AAAI 2025)
Kyungjin Cho and Eunjin Oh, Mimicking Networks for Constrained Multicuts in Hypergraphs. (ISAAC 2024)
Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song ,
Dynamic Parameterized Problems on Unit Disk Graphs. (ISAAC 2024)
Shinwoo An, Eunjin Oh, and Jie Xue, Sparse Outerstring Graphs Have Logarithmic Treewidth. (ESA 2024)
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)

Selected Conference Papers (2015-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)

Journal Papers (2020-Current)

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

Page updated

Google Sites

Report abuse