Hee-Kap Ahn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Hee-Kap Ahn has a total of 144 co-authors. Here are the top co-authors by number of shared publications:
- Sang Won Bae
Kyonggi Univ, Div Comp Sci & Engn, Suwon, South Korea
30 shared publications - Chan-Su Shin
Hankuk University of Foreign Studies
19 shared publications - Antoine Vigneron
UNIST, Sch Elect & Comp Engn, Ulsan, South Korea
18 shared publications Otfried Cheong
KAIST
14 shared publications- Eunjin Oh
POSTECH, Dept Comp Sci & Engn, Pohang, South Korea
12 shared publications Wanbin Son
12 shared publications
Latest Publications
- Open Access
- 17 August 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (4) , 2362-2398
Minimum Partition of Polygons under Width and Cut Constraints
- 17 August 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (4) , 2362-2398
Open AccessMinimum Partition of Polygons under Width and Cut Constraints
- 14 February 2026
- Published by Springer Nature
- p. 418-431
Shortcutting the Diameter of a Polygon
- 7 December 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1063
Largest similar copies of convex polygons in polygonal domains
- 7 December 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1063
Largest similar copies of convex polygons in polygonal domains
- 20 November 2025
- Published by Elsevier in Computational Geometry
- Vol. 133
Inscribed and circumscribed histogons of a convex polygon
- 20 November 2025
- Published by Elsevier in Computational Geometry
- Vol. 133
Inscribed and circumscribed histogons of a convex polygon
- Open Access
Minimum Partition of Polygons under Width and Cut Constraints
We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of unit vectors if the length of the orthogonal projection of the polygon on a line parallel to a vector in the set is at most one. We analyze structural properties of the minimum partition numbers, focusing on monotonicity under polygon containment. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a consequence, we prove a partition analogue of Bang's conjecture about coverings of convex regions in the plane: for any partition of a convex body in the plane, the sum of relative widths of all parts is at least one. For any convex polygon, there exists a direction along which an optimal partition is achieved by parallel cuts. Given such a direction, an optimal partition can be computed in linear time.
Open AccessMinimum Partition of Polygons under Width and Cut Constraints
We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of unit vectors if the length of the orthogonal projection of the polygon on a line parallel to a vector in the set is at most one. We analyze structural properties of the minimum partition numbers, focusing on monotonicity under polygon containment. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a consequence, we prove a partition analogue of Bang's conjecture about coverings of convex regions in the plane: for any partition of a convex body in the plane, the sum of relative widths of all parts is at least one. For any convex polygon, there exists a direction along which an optimal partition is achieved by parallel cuts. Given such a direction, an optimal partition can be computed in linear time.
- 18 July 2025
- Published by Springer Nature
- p. 72-85
Monotone Partitions of Simple Polygons
- 26 June 2025
- Published by Elsevier in Computational Geometry
- Vol. 131
Guarding points on a terrain by watchtowers
- 26 June 2025
- Published by Elsevier in Computational Geometry
- Vol. 131
Guarding points on a terrain by watchtowers
- Open Access
Guarding Terrains with Guards on a Line
Given an $x$-monotone polygonal chain $T$ with $n$ vertices, and an integer $k$, we consider the problem of finding the lowest horizontal line $L$ lying above $T$ with $k$ point guards lying on $L$, so that every point on the chain is \emph{visible} from some guard. A natural optimization is to minimize the $y$-coordinate of $L$. We present an algorithm for finding the optimal placements of $L$ and $k$ point guards for $T$ in $O(k^2λ_{k-1}(n)\log n)$ time for even numbers $k\ge 2$, and in $O(k^2λ_{k-2}(n)\log n)$ time for odd numbers $k \ge 3$, where $λ_{s}(n)$ is the length of the longest $(n,s)$-Davenport-Schinzel sequence. We also study a variant with an additional requirement that $T$ is partitioned into $k$ subchains, each subchain is paired with exactly one guard, and every point on a subchain is visible from its paired guard. When $L$ is fixed, we can place the minimum number of guards in $O(n)$ time. When the number $k$ of guards is fixed, we can find an optimal placement of $L$ with $k$ point guards lying on $L$ in $O(kn)$ time.Open AccessGuarding Terrains with Guards on a Line
Given an $x$-monotone polygonal chain $T$ with $n$ vertices, and an integer $k$, we consider the problem of finding the lowest horizontal line $L$ lying above $T$ with $k$ point guards lying on $L$, so that every point on the chain is \emph{visible} from some guard. A natural optimization is to minimize the $y$-coordinate of $L$. We present an algorithm for finding the optimal placements of $L$ and $k$ point guards for $T$ in $O(k^2λ_{k-1}(n)\log n)$ time for even numbers $k\ge 2$, and in $O(k^2λ_{k-2}(n)\log n)$ time for odd numbers $k \ge 3$, where $λ_{s}(n)$ is the length of the longest $(n,s)$-Davenport-Schinzel sequence. We also study a variant with an additional requirement that $T$ is partitioned into $k$ subchains, each subchain is paired with exactly one guard, and every point on a subchain is visible from its paired guard. When $L$ is fixed, we can place the minimum number of guards in $O(n)$ time. When the number $k$ of guards is fixed, we can find an optimal placement of $L$ with $k$ point guards lying on $L$ in $O(kn)$ time. - Open Access
Stacking Monotone Polytopes
This paper addresses the problem of computing the optimal stacking of two monotone polytopes P and Q in . A monotone polytope in is defined as a polytope whose intersection with any line parallel to the last coordinate axis is connected, and the stacking of P and Q is defined as a translation of Q, such that “Q touches P from above”. To evaluate the stack, we use three different scoring criteria: (1) the height of the stack, (2) the maximum pointwise distance along the -axis, and (3) the volume between P and Q. We propose exact algorithms to compute the optimal stacking for each scoring criterion.Open AccessStacking Monotone Polytopes
This paper addresses the problem of computing the optimal stacking of two monotone polytopes P and Q in . A monotone polytope in is defined as a polytope whose intersection with any line parallel to the last coordinate axis is connected, and the stacking of P and Q is defined as a translation of Q, such that “Q touches P from above”. To evaluate the stack, we use three different scoring criteria: (1) the height of the stack, (2) the maximum pointwise distance along the -axis, and (3) the volume between P and Q. We propose exact algorithms to compute the optimal stacking for each scoring criterion.