87 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Pohang University of Science and TechnologyKR6 papers
- Dongguk UniversityKR5 papers
- Seoul National UniversityKR5 papers
- Korea Advanced Institute of Science and TechnologyKR4 papers
- Yeungnam UniversityKR4 papers
- The University of SydneyAU3 papers
- Tohoku UniversityJP3 papers
- Université Libre de BruxellesBE3 papers
- University of Electro-CommunicationsJP3 papers
- Utah State UniversityUS3 papers
- Yonsei UniversityKR3 papers
- Carleton UniversityCA2 papers
13 papers · 1 filter
Computing a Geodesic Two-Center of Points in a Simple Polygon
Eunjin Oh, Sang Won Bae, Hee-Kap Ahn
Given a simple polygon and a set of points contained in , we consider the geodesic -center problem where we want to find points, called \emph{centers}, in to…
Shortest Path Queries in Simple Polygons
Sang Won Bae, Haitao Wang
Let be a simple polygon of vertices. We consider two-point shortest path queries in . We build a data structure of size in time such that given any t…
Closest-Pair Queries in Fat Rectangles
Sang Won Bae, Michiel Smid
In the range closest pair problem, we want to construct a data structure storing a set of points in the plane, such that for any axes-parallel query rectangle , the clos…
Faster Algorithms for Growing Prioritized Disks and Rectangles
Hee-Kap Ahn, Sang Won Bae, Jongmin Choi +6
Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of disks in the plane. Initially, all disks have r…
Computing the Geodesic Diameter and Center of a Polygonal Domain
Sang Won Bae, Matias Korman, Joseph S. B. Mitchell +3
For a polygonal domain with holes and a total of vertices, we present algorithms that compute the geodesic diameter in time and the geodesic center…
Computing the Geodesic Centers of a Polygonal Domain
Sang Won Bae, Matias Korman, Yoshio Okamoto
We present an algorithm that computes the geodesic center of a given polygonal domain. The running time of our algorithm is for any , where is the number of…
Improved Bounds for Beacon-Based Coverage and Routing in Simple Rectilinear Polygons
Sang Won Bae, Chan-Su Shin, Antoine Vigneron
We establish tight bounds for beacon-based coverage problems, and improve the bounds for beacon-based routing problems in simple rectilinear polygons. Specifically, we show that $\…
Theta-3 is connected
Oswin Aichholzer, Sang Won Bae, Luis Barba +5
In this paper, we show that the -graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.
Computing the Geodesic Diameter and Center of a Simple Polygon in Linear Time
Sang Won Bae, Matias Korman, Yoshio Okamoto +1
In this paper, we show that the geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric proper…
A Generalization of the Convex Kakeya Problem
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong +3
Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be se…
The Geodesic Diameter of Polygonal Domains
Sang Won Bae, Matias Korman, Yoshio Okamoto
This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corn…
Querying Two Boundary Points for Shortest Paths in a Polygonal Domain
Sang Won Bae, Yoshio Okamoto
We consider a variant of two-point Euclidean shortest path query problem: given a polygonal domain, build a data structure for two-point shortest path query, provided that query po…
Covering Points by Disjoint Boxes with Outliers
Hee-Kap Ahn, Sang Won Bae, Erik D. Demaine +5
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…