Covering Points by Disjoint Boxes with Outliers (2009)
Ahn, Hee-Kap, Bae, Sang Won, Demaine, Erik D., Demaine, Martin L., Kim, Sang-Sub, Korman, Matias, ...
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...
Spatial Skyline Queries: An Efficient Geometric Algorithm (2009)
Son, Wanbin, Lee, Mu-Woong, Ahn, Hee-Kap, Hwang, Seung-won
As more data-intensive applications emerge, advanced retrieval semantics, such as ranking or skylines, have attracted attention. Geographic information systems are such an application with massive...
Aperture-Angle and Hausdorff-Approximation of Convex Figures (2008)
Ahn, Hee-Kap, Bae, Sang Won, Cheong, Otfried, Gudmundsson, Joachim
The aperture angle α(x,Q) of a point x /∈ 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...
River networks and watershed maps of triangulated terrains revisited ∗ (2008)
Hee-kap Ahn, Mark Berg, Otfried Cheong, Herman Haverkort, Laura Toma
Triangulated surfaces are often used to represent terrains in geographic information systems. We investigate the complexity of river networks and watershed maps on such terrains under the assumption...
Casting an Object with a Core ∗ (2008)
Hee-kap Ahn, Sang Won, Bae Siu-wing
This paper addresses geometric problems that concern manufacturing an object using a cast with a core. In casting, molten material is poured into the cavity of the cast and allowed to solidify. The...
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Jack Snoeyink
We propose a hull operator, the reflex-free hull, that allows us to define a 3D analogue to bays in polygons. The reflex-free hull allows a rich set of topological types, yet for polyhedral input...
Aperture-Angle and Hausdorff-Approximation of Convex Figures (2008)
Hee-kap Ahn, Sang Won, Bae Otfried, Cheong Joachim Gudmundsson
The aperture angle α(x, Q) of a point x � ∈ 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...
Hee-kap Ahn, Peter Brass, Otfried Cheong, Hyeon-suk Na, Chan-su Shin, Antoine Vigneron
Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in P, and the smallest such set S ′ that...
Abstract Competitive Facility Location: The Voronoi Game ⋆ (2008)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin, René Oostrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P, a flipturn involves reflecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grünbaum (1995)) showed that any polygon on n vertices...
1 Introduction Casting with Skewed Ejection Direction Revisited (2008)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong
The manufacturing industry has at its disposal a number of processes for constructing objects, including gravity casting,
A Geometric Proof on Shortest Paths of Bounded Curvature (2008)
Ahn, Hee-Kap, Bae, Sang-Won, Cheong, Otfried
A point-wise car-like robot moving in the plane changes its direction with a constraint on turning curvature. In this paper, we consider the problem of computing a shortest path of bounded curvature...
Hee-kap Ahn, Mark De Berg, Siu-wing Cheng, Dan Halperin, Otfried Schwarzkopf
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
z Universite du Quebec a Hull.
Hee-kap Ahn, Mark De Berg, Siu-wing Cheng, Dan Halperin, Otfried Schwarzkopf
We study geometric problems that arise in casting. Casting is a manufacturing process where liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid...
Building Bridges Between Convex Regions* (2007)
Hee-kap Ahn, Otfried Cheong, Chan-su Shin
In the Euclidean traveling salesman and buyers problem (TSBP), we are given a set of convex regions in d-dimensional space, and we wish to find a minimum-cost tour that visits all the regions. The...
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Jack Snoeyink
We define a reflex-free hull in three dimensions as an intersection of reflex-free sets. The reflex-free hull allows a rich set of topological types, yet for polyhedral input with n edges, it remains...
In the Euclidean traveling salesman and buyers problem (TSBP), we are given a set of convex regions in d-dimensional space, and we wish to nd a minimum-cost tour that visits all the regions. The cost...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Figure 1: An example of a ipturn. Given a polygon P, a ipturn involves re ecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed...
Maximizing the Overlap of Two Planar Convex Sets under Rigid Motions (2007)
Ahn, Hee-Kap, Cheong, Otfried, Park, Chong-Dae, Shin, Chan-Su, Vigneron, Antoine
Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε>0, we compute a rigid...
Constructing Optimal Highways (2007)
Ahn, Hee-Kap, Alt, Helmut, Asano, Tetsuo, Bae, Sang Won, Brass, Peter, Cheong, Otfried, ...
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...
Aperture-Angle and Hausdorff-Approximation of Convex Figures (2007)
Ahn, Hee-Kap, Bae, Sang Won, Cheong, Otfried, Gudmundsson, Joachim
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...
Dilation-optimal edge deletion in polygonal cycles (2007)
Hee-kap Ahn, Mohammad Farshi, Christian Knauer, Michiel Smid, Yajun Wang
Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them....
Casting with Skewed Ejection Direction (2006)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried
Casting is a manufacturing process in which liquid is poured into a cast (mold) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is...
Ahn, Hee-Kap, Brass, Peter, Cheong, Otfried, Na, Hyeon-Suk, Shin, Chan-Su, Vigneron, Antoine
Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S′ that...
Casting with skewed ejection direction (2006)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried
Casting is a manufacturing process in which liquid is poured into a cast (mould) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is...
Casting an object with a core (2005)
Ahn, Hee-Kap, Bae, Sang Won, Cheng, Siu-Wing, Chwa, Kyung-Yong
This paper addresses geometric problems in manufacturing objects by casting. In casting, molten material is poured into the cavity of the cast and allowed to solidify, after which the cast is...
Casting an object with a core (2005)
Ahn, Hee-Kap, Cheng, Siu-Wing, Bae, Sang Won, Chwa, Kyung-Yong
This paper addresses geometric problems that concern manufacturing an object using a cast with a core. In casting, molten material is poured into the cavity of the cast and allowed to solidify. The...
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Snoeyink, Jack
We propose a hull operator, the reflex-free hull, that allows us to define a 3D analogue to bays in polygons. The reflex-free hull allows a rich set of topological types, yet for polyhedral input...
Casting a Polyhedron with Directional Uncertainty (2003)
Ahn, Hee-Kap, Cheong, Otfried, Van Oostrum, René
Casting is a manufacturing process in which molten material is poured into a cast (mould), which is opened after the material has solidified. As in all applications of robotics, we have to deal with...
Building Bridges Between Convex Regions (2003)
Ahn, Hee-Kap, Cheong, Otfried, Shin, Chan-Su
In the Euclidean traveling salesman and buyers problem (TSBP), we are given a set of convex regions in d-dimensional space, and we wish to find a minimum-cost tour that visits all the regions. The...
Competitive Facility Location: The Voronoi Game (2003)
Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, Rene Van Oostrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Separating an Object from its Cast (2002)
Ahn, Hee-Kap, De Berg, Mark, Bose, Prosenjit, Cheng, Siu-Wing, Halperin, Dan, Matousek, Jirí, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Competitive Facility Location along a Highway (2001)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Golin, Mordecai, Van Oostrum, René
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Competitive facility location: the Voronoi game. (2001)
Oostrum, R. Van, Ahn, Hee-Kap, Cheong, O., Golin, M.
Abstract. We consider a competitive facility location problem with two players.Pla yers alternate placing points, one at a time, into the playing arena, until each of them has placed n points.The...
A survey on multidimensional access methods (2001)
Hee-kap Ahn, Hee Kap Ahn, Nikos Mamoulis, Nikos Mamoulis, Ho Min Wong, Ho Min Wong
The extraordinary format of spatial data and the fact that there is no straightforward mapping of spatial objects from the multidimensional space to the 1-dimensional space, stimulated various...
Oostrum. Competitive facility location along a highway (2001)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin, Rend Costrum
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Oostrum. Competitive facility location along a highway (2001)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin
, and Ren'e van Oostrum 1
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. We show that any polygon on n vertices will be convex after any sequence of at most n(n 3)=2...
Reachability By Paths of Bounded Curvature in Convex Polygons (2000)
Hee-Kap Ahn, Otfried Cheong, Ji R Matousek, Antoine Vigneron
Let B be a point robot moving in the plane, whose path is constrained to forward motions with a curvature at most 1, and let P be a convex polygon with n vertices. Given a starting conguration (a...
Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Oostrum, R. Van, Ahn, Hee-Kap, Golin, Mordecai
A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray...
Casting with Skewed Ejection Direction Revisited (1999)
Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong
this paper we improve the running time to O(n
Casting with skewed ejection direction (1998)
Hee-kap Ahn, Siu-wing Cheng, Otfried Cheong
Casting is a manufacturing process in which liquid is poured into a cast (mould) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is...
Separating an Object from its Cast (1998)
Hee-kap Ahn, Mark De Berg, Siu-Wing Cheng, Jiri Matousek, Dan Halperin, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Casting with Skewed Ejection Direction (1998)
Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong
. Casting is a manufacturing process in which liquid is poured into a cast (mould) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is...
Separating an Object from its Cast (1997)
Hee-kap Ahn, Mark De Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...