Source author record

Hee-Kap Ahn

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 math.MG

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Farthest-point Voronoi diagrams in the presence of rectangular obstacles

We present an algorithm to compute the geodesic $L_1$ farthest-point Voronoi diagram of $m$ point sites in the presence of $n$ rectangular obstacles in the plane. It takes $O(nm+n \log n + m\log m)$ construction time using $O(nm)$ space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in $O(\log(n+m))$ time.

preprint2020arXiv

Efficient Planar Two-Center Algorithms

We consider the planar Euclidean two-center problem in which given $n$ points in the plane we are to find two congruent disks of the smallest radius covering the points. We present a deterministic $O(n \log n)$ -time algorithm for the case that the centers of the two optimal disks are close to each other, that is, the overlap of the two optimal disks is a constant fraction of the disk area. We also present a deterministic $O(n\log n)$ -time algorithm for the case that the input points are in convex position. Both results improve the previous best $O(n\log n\log\log n)$ bound on the problems.

preprint2020arXiv

Largest triangles in a polygon

We study the problem of finding maximum-area triangles that can be inscribed in a polygon in the plane. We consider eight versions of the problem: we use either convex polygons or simple polygons as the container; we require the triangles to have either one corner with a fixed angle or all three corners with fixed angles; we either allow reorienting the triangle or require its orientation to be fixed. We present exact algorithms for all versions of the problem. In the case with reorientations for convex polygons with $n$ vertices, we also present $(1-\varepsilon)$ -approximation algorithms.

preprint2015arXiv

A linear-time algorithm for the geodesic center of a simple polygon

Given two points in a simple polygon $P$ of $n$ vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within $P$ . The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$ . In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an $O(n\log n)$ -time algorithm that computes the geodesic center of $P$ . Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

preprint2012arXiv

A Generalization of the Convex Kakeya Problem

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 seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(n log n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.

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.

preprint2010arXiv

Reachability by Paths of Bounded Curvature in a Convex Polygon

Let $B$ be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most one, and let $P$ be a convex polygon with $n$ vertices. Given a starting configuration (a location and a direction of travel) for $B$ inside $P$ , we characterize the region of all points of $P$ that can be reached by $B$ , and show that it has complexity $O(n)$ . We give an $O(n^2)$ time algorithm to compute this region. We show that a point is reachable only if it can be reached by a path of type CCSCS, where C denotes a unit circle arc and S denotes a line segment.

preprint2007arXiv

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).

preprint2007arXiv

Constructing Optimal Highways

For two points $p$ and $q$ in the plane, a straight line $h$ , called a highway, and a real $v>1$ , we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the time needed to traverse a quickest path from $p$ to $q$ , where the distance is measured with speed $v$ on $h$ and with speed 1 in the underlying metric elsewhere. Given a set $S$ of $n$ points in the plane and a highway speed $v$ , we consider the problem of finding a \emph{highway} that minimizes the maximum travel time over all pairs of points in $S$ . If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $L_1$ - and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $O(n^{2} \log n)$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.

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.

Hee-Kap Ahn

Research overview

Is this your work?

10 publications

Farthest-point Voronoi diagrams in the presence of rectangular obstacles

Efficient Planar Two-Center Algorithms

Largest triangles in a polygon

A linear-time algorithm for the geodesic center of a simple polygon

A Generalization of the Convex Kakeya Problem

Covering and Piercing Disks with Two Centers

Covering Points by Disjoint Boxes with Outliers

Reachability by Paths of Bounded Curvature in a Convex Polygon

Aperture-Angle and Hausdorff-Approximation of Convex Figures

Constructing Optimal Highways

See the researcher in context

Building this map preview