Eunjin Oh

activity

20172022

collaborators

Showing cs.CGShow all

16 papers · 1 filter

cs.CG2021

Feedback Vertex Set on Geometric Intersection Graphs

Shinwoo An, Eunjin Oh

In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size $k$ , if it exists, which runs in time $2^{O (k)} (n + m)$ , where $n$ and…

cs.CG2021

Linear-Time Approximation Scheme for k-Means Clustering of Affine Subspaces

Kyungjin Cho, Eunjin Oh

In this paper, we present a linear-time approximation scheme for $k$ -means clustering of \emph{incomplete} data points in $d$ -dimensional Euclidean space. An \emph{incomplete} data…

cs.CG2021

Reachability Problems for Transmission Graphs

Shinwoo An, Eunjin Oh

Let $P$ be a set of $n$ points in the plane where each point $p$ of $P$ is associated with a radius $r_{p} > 0$ .The transmission graph $G = (P, E)$ of $P$ is defined as the directed graph…

cs.CG2020

The Maximum-Level Vertex in an Arrangement of Lines

Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn +2

Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A (L)$ of maximum…

cs.CG2019

Computing a Geodesic Two-Center of Points in a Simple Polygon

Eunjin Oh, Sang Won Bae, Hee-Kap Ahn

Given a simple polygon $P$ and a set $Q$ of points contained in $P$ , we consider the geodesic $k$ -center problem where we want to find $k$ points, called \emph{centers}, in $P$ to…

cs.CG2019

Computing the Center Region and Its Variants

Eunjin Oh, Hee-Kap Ahn

We present an $O (n^{2} lo g^{4} n)$ -time algorithm for computing the center region of a set of $n$ points in the three-dimensional Euclidean space. This improves the previously best kno…