47 Result(s)
within
Hee-Kap Ahn
English
Algorithm Analysis and Problem Complexity
-
Article
Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles
We present an algorithm to compute the geodesic \(L_1\) L 1 ...
-
Chapter and Conference Paper
Efficient k-Center Algorithms for Planar Points in Convex Position
We present an efficient algorithm for the planar k-center problem for points in convex position under the Euclidean distance. Given n points in convex position in the plane, our algorithm computes k congruent dis...
-
Article
Maximizing Dominance in the Plane and its Applications
Given a set P of n weighted points, a set Q of m points in the plane, and a positive integer k, we consider the optimization problem of finding a subset of Q with at most k points that dominates a subset of P wit...
-
Chapter and Conference Paper
Covering Convex Polygons by Two Congruent Disks
We consider the planar two-center problem for a convex polygon: given a convex polygon in the plane, find two congruent disks of minimum radius whose union contains the polygon. We present an
-
Chapter and Conference Paper
Intersecting Disks Using Two Congruent Disks
We consider the Euclidean 2-center problem for a set of n disks in the plane: find two smallest congruent disks such that every disk in the set intersects at least one of the two congruent disks. We present a det...
-
Article
The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest s...
-
Article
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms
Given a read-only memory for input and a write-only stream for output, an s-workspace algorithm, for a positive integer parameter s, is an algorithm using only O(s) words of workspace in addition to the memory fo...
-
Chapter and Conference Paper
Maximizing Dominance in the Plane and Its Applications
Given a set P of n points with weights (possibly negative), a set Q
-
Chapter and Conference Paper
Minimum-Width Annulus with Outliers: Circular, Square, and Rectangular Cases
We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and a nonnegative integer ...
-
Chapter and Conference Paper
Minimum-Width Square Annulus Intersecting Polygons
For k (possibly overlap**) polygons of total complexity n in the plane, we present an algorithm for computing a minimum-width square annulus that intersects all input polygons in
-
Chapter and Conference Paper
Polygon Queries for Convex Hulls of Points
We study the following range searching problem: Preprocess a set P of n points in the plane with respect to a set \(\mathcal {O}\) ...
-
Chapter and Conference Paper
A Time-Space Trade-Off for Triangulations of Points in the Plane
In this paper, we consider time-space trade-offs for reporting a triangulation of points in the plane. The goal is to minimize the amount of working space while kee** the total running time small. We present...
-
Chapter and Conference Paper
Computing the Center Region and Its Variants
We present an \(O(n^2\log ^4 n)\) -time algorithm for computing the center region of a set of n points in th...
-
Chapter and Conference Paper
Bundling Two Simple Polygons to Minimize Their Convex Hull
Given two simple polygons P and Q in the plane, we study the problem of finding a placement \(\varphi P\) o...
-
Article
Guest Editor’s Foreword
-
Chapter and Conference Paper
A Middle Curve Based on Discrete Fréchet Distance
Given a set of polygonal curves we seek to find a middle curve that represents the set of curves. We require that the middle curve consists of points of the input curves and that it minimizes the discrete Fréc...
-
Chapter and Conference Paper
Computing a Geodesic Two-Center of Points in a Simple Polygon
Given a simple polygon P and a set Q of points contained in P, we consider the geodesic k-center problem in which we seek to find k points, called centers, in P to minimize the maximum geodesic distance of any po...
-
Chapter and Conference Paper
Geometric Matching Algorithms for Two Realistic Terrains
We consider a geometric matching of two realistic terrains, each of which is modeled as a piecewise-linear bivariate function. For two realistic terrains f and g where the domain of g is relatively larger than th...
-
Chapter and Conference Paper
The 2-Center Problem in a Simple Polygon
The geodesic k-center problem in a simple polygon with n vertices consists in the following. Find k points, called centers, in the polygon to minimize the maximum geodesic distance from any point of the polygon t...
-
Article
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 Kak...
