Source author record

Sang-Sub Kim

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Computing Euclidean k-Center over Sliding Windows

In the Euclidean $k$ -center problem in sliding window model, input points are given in a data stream and the goal is to find the $k$ smallest congruent balls whose union covers the $N$ most recent points of the stream. In this model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. Cohen-Addad et al.~\cite{cohen-2016} gave a $(6+ε)$ -approximation for the metric $k$ -center problem using O( $k/ε\log α$ ) points, where $α$ is the ratio of the largest and smallest distance and is assumed to be known in advance. In this paper, we present a $(3+ε)$ -approximation algorithm for the Euclidean $1$ -center problem using O( $1/ε\log α$ ) points. We present an algorithm for the Euclidean $k$ -center problem that maintains a coreset of size $O(k)$ . Our algorithm gives a $(c+2\sqrt{3} + ε)$ -approximation for the Euclidean $k$ -center problem using O( $k/ε\log α$ ) points by using any given $c$ -approximation for the coreset where $c$ is a positive real number. For example, by using the $2$ -approximation~\cite{feder-greene-1988} of the coreset, our algorithm gives a $(2+2\sqrt{3} + ε)$ -approximation ( $\approx 5.465$ ) using $O(k\log k)$ time. This is an improvement over the approximation factor of $(6+ε)$ by Cohen-Addad et al.~\cite{cohen-2016} with the same space complexity and smaller update time per point. Moreover we remove the assumption that $α$ is known in advance. Our idea can be adapted to the metric diameter problem and the metric $k$ -center problem to remove the assumption. For low dimensional Euclidean space, we give an approximation algorithm that guarantees an even better approximation.

preprint2012arXiv

Covering and Piercing Disks with Two Centers

We give exact and approximation algorithms for two-center problems when the input is a set $\mathcal{D}$ of disks in the plane. We first study the problem of finding two smallest congruent disks such that each disk in $\mathcal{D}$ intersects one of these two disks. Then we study the problem of covering the set $\mathcal{D}$ by two smallest congruent disks.

preprint2010arXiv

Covering Points by Disjoint Boxes with Outliers

For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general p we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number p, we give algorithms that find the solution in the following running times: For squares we have O(n+k log k) time for p=1, and O(n log n+k^p log^p k time for p = 2,3. For rectangles we get O(n + k^3) for p = 1 and O(n log n+k^{2+p} log^{p-1} k) time for p = 2,3. In all cases, our algorithms use O(n) space.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.