Author name cluster

Sang Won Bae

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

TCS Journal 2025 Journal Article

On k -enclosing slab problems

Taehoon Ahn
Sang Won Bae

Given a set P of n points in R d for d ⩾ 2 and an integer parameter 0 ⩽ k ⩽ n, a slab, the volume between two parallel hyperplanes, is called k -enclosing if it encloses k points of P. We consider the problem of finding an optimal k -enclosing slab for P with minimum or maximum width. In this paper, we present two simple algorithmic approaches based on our new characterization of optimal slabs. Our first approach yields an O ( n 3 log n ) -time algorithm in R 3 and an O ( n d log 2 n ) -time algorithm in R d, independently of k, for any constant d ⩾ 3. These algorithms also work properly for the weighted variant of the problems in the same time bound. By our second approach, we present faster algorithms for d ⩽ 3 when k is relatively small or large. More specifically, our algorithms solve both the minimum and maximum problems in R 3 in O ( ( k + 1 ) 1 / 3 n 3 ) time for small k < n / 2 and in O ( min { ( n − k + 1 ) 1 / 3 n 3, ( n − k + 1 ) 7 / 3 n 2 } ) time for large k > n / 2. In particular, for large k > n / 2, we further show that the minimization problem in R 3 can be solved even faster in O ( ( n − k + 1 ) 3 n 3 / 2 + ϵ ) time. We also discuss the planar case d = 2 in which the minimum and maximum problems can be solved in O ( n log n + ( n − k + 1 ) n ) time for any 0 ⩽ k ⩽ n.

Details DOI

TCS Journal 2020 Journal Article

Minimum-width double-strip and parallelogram annulus

Sang Won Bae

In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are O ( n 2 ) and O ( n 3 log ⁡ n ) -time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.

Details DOI

TCS Journal 2019 Journal Article

L1 shortest path queries in simple polygons

Sang Won Bae
Haitao Wang

Let P be a simple polygon of n vertices. We consider two-point L 1 shortest path queries in P. We build a data structure of O ( n ) size in O ( n ) time such that given any two query points s and t, the length of an L 1 shortest path from s to t in P can be computed in O ( log ⁡ n ) time, or in O ( 1 ) time if both s and t are vertices of P, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.

Details DOI

TCS Journal 2018 Journal Article

Computing a minimum-width square annulus in arbitrary orientation

Sang Won Bae

In this paper, we address the problem of computing a minimum-width square annulus in arbitrary orientation that encloses a given set of n points in the plane. A square annulus is the region between two concentric squares. We present an O ( n 3 log ⁡ n ) -time algorithm that finds such a square annulus over all orientations.

Details DOI

TCS Journal 2018 Journal Article

Covering points with convex sets of minimum size

Sang Won Bae
Hwan-Gue Cho
William Evans
Noushin Saeedi
Chan-Su Shin

For a set P of n points in the plane, we present algorithms for finding two bounded convex sets that cover P such that the total area or perimeter of the convex sets is minimized in O ( n 4 log ⁡ n ) and O ( n 2 log ⁡ n ) time, respectively. The former is the first result for minimum total area, and the latter is an improvement on the fastest previous algorithm for minimum total perimeter, which runs in O ( n 3 ) time [24]. We also extend our algorithms to find k ⩾ 2 convex sets minimizing area in O ( n 2 k ( k − 1 ) log ⁡ n ) time. The algorithms can be applied to detect road intersections from the GPS trajectories of moving vehicles for automated map generation or partial clustering.

Details DOI

TCS Journal 2018 Journal Article

Gap-planar graphs

Sang Won Bae
Jean-Francois Baffier
Jinhee Chun
Peter Eades
Kord Eickmeyer
Luca Grilli
Seok-Hee Hong
Matias Korman

We introduce the family of k-gap-planar graphs for k ≥ 0, i. e. , graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

Details DOI

TCS Journal 2018 Journal Article

On finding a longest common palindromic subsequence

Sang Won Bae
Inbok Lee

Recently, Chowdhury et al. [5] proposed the longest common palindromic subsequence problem. It is a variant of the well-known LCS problem, which refers to finding a palindromic LCS between two strings T 1 and T 2. In this paper, we present a new O ( n + R 2 ) -time algorithm where n = | T 1 | = | T 2 | and R is the number of matches between T 1 and T 2. We also show that the average running time of our algorithm is O ( n 4 / | Σ | 2 ), where Σ is the alphabet of T 1 and T 2. This improves the previously best algorithms whose running times are O ( n 4 ) and O ( R 2 log 2 ⁡ n log ⁡ log ⁡ n ).

Details DOI

TCS Journal 2015 Journal Article

Group nearest-neighbor queries in the L 1 plane

Wanbin Son
Sang Won Bae
Hee-Kap Ahn

Let P be a set of n points in the plane. The k-nearest-neighbor (abbreviated as k-NN) query problem is to preprocess P into a data structure that quickly reports k closest points in P for a query point q. This paper addresses a generalization of the k-NN query problem to a query set Q of points, namely, the group k-nearest-neighbor query problem, in the L 1 plane. More precisely, a query is assigned with a set Q of at most m points and a positive integer k with k ≤ n, and the distance between a point p of P and a query set Q is defined as the sum of L 1 distances from p to all q ∈ Q. The maximum number m of query points Q is assumed to be known in advance and to be at most n. In this paper, we propose two algorithms, one based on the range tree and the other based on a data structure for segment dragging queries, and obtain the following complexity bounds: (1) a group k-NN query can be handled in O ( T min log ⁡ n + ( k + m 2 ) ( log ⁡ log ⁡ n + log ⁡ m ) ) time after preprocessing P using O ( m 2 n log 2 ⁡ n ) space, where T min = min ⁡ { k + m, m 2 }, or (2) a group k-NN query can be handled in O ( ( k + m ) log 2 ⁡ n + m 2 ( log ϵ ⁡ n + log ⁡ m ) ) time after preprocessing P using O ( m 2 n ) space, where ϵ > 0 is an arbitrarily small constant. We also show that our approach can be applied to the weighted group k-nearest-neighbor query problem and the group k-farthest-neighbor query problem.

Details DOI