Eunjin Oh

I am an associate professor at the Department of Computer Science and Engineering, POSTECH. Before joining POSTECH, I was a postdoctoral fellow at Max Planck Institute for Informatics, hosted by Kurt Mehlhorn. I completed my Ph.D. from POSTECH in 2018.

My research interests lie in algorithms, data structures, and computational geometry. More specifically, I am interested in shortest path problems in simple polygons, point location problems, and dynamic data structures for geometric objects.

Selected Publications

(A complete list can be found here)

• Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners. AAAI2024 ( with Kyungjin Cho and Jihun Shin)

• Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs.  ESA2023 ( with Seunghyeok Oh)

• Faster Algorithms for Cycle Hitting Problems on Disk Graphs  WADS 2023. (with Shinwoo An and Kyungjin Cho)

• Parameterized Algorithms for the Planar Disjoint Paths Problem: Exponential in k^2 and Linear in n.  SODA 2023. (with Kyungjin Cho and Seunghyeok Oh)

• The Maximum-Level Vertex in an Arrangement of Lines. Discrete & Computational Geometry. (with Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn, Micha Sharir)

• Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces.. ISAAC 2021. (with Kyungjin Cho)

• Feedback Vertex Set in Unit Disk Graphs. ISAAC 2021. (with Shinwoo An)

• Reachability Oracles in Geometric Tranmission Graphs. WADS 2021 and Algorithmica. (with Shinwoo An) 

• Shortest Path Queries in Geometric Networks. ISAAC 2020. (single author)

• Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams. SODA 2019. (single author)

• Minimizing Distance-to-Sight in Polygonal Domains,  ISAAC 2018. (single author)

• Point Location in Incremental Planar Subdivisions.  ISAAC 2018. (single author)

• Approximate range clustering queries, SoCG 2018. (with Hee-Kap Ahn)

• Point location in dynamic planar subdivisions. SoCG 2018. (with Hee-Kap Ahn)

• Dynamic geodesic convex hulls in dynamic simple polygons,  SoCG 2017. (with Hee-Kap Ahn)

• Voronoi diagrams for a moderate-sized point-set in a simple polygon, SoCG 2017. (with Hee-Kap Ahn)

• The farthest-point geodesic Voronoi diagram for points on the boundary of a simple polygon, SoCG 2016. (with Luis Barba and Hee-Kap Ahn)

• A linear-time algorithm for the geodesic center of a simple polygon, SoCG 2015 and Discrete & Computational Geometry. (with Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou de Carufel, Matias Korman)

Academic Activities

Program Comittee

• ISAAC 2023, ESA 2023, SOSA 2023, WAOA 2022, MFCS 2021, CG:YRF 21, SoCG 20, EuroCG19
  
  

Reviewer

• WADS 2023, GD 2022, ISAAC 2021, ISAAC 2020, ICALP 2020, WG 2020, SWAT 2020

• Computing in Geometry and Topology, Computatioanl Geometry: Theory and Applications, Discrete and Computational Geometry, ACM Transactions on Algorithms,
  Algorithmica,

Contact

Office:  Room 229,  Building 2,

77 Cheongam-Ro, Nam-Gu, Pohang, Gyeongbuk, Republic of Korea, ZIP: 37673

Email:  eunjin.oh@postech.ac.kr  

Phone: (+82) 054-279-2389