Browsing by Author "LEE, HS"

Now showing 1 - 4 of 4

APPROXIMATING VERTICES OF A CONVEX POLYGON WITH GRID POINTS IN THE POLYGON
(1992)
LEE, HS
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider the problem of approximating a vertex of a convex polygon by an integer point in the polygon. We show that the nearest grid point in a convex polygon to a vertex can be found if it exists, or decided to be nonexistent, in time O(n + logl), where l is the diameter of the polygon and a is the number of the polygon's vertices. The underlying technique used in the continued fraction expansion.
COVERING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES
(1992)
LEE, HS
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a closed region bounded by a convex polygon P with n vertices such that size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + log m) approximation algorithm which guarantees finite performance ratio.
FINDING A MAXIMUM SET OF INDEPENDENT CHORDS IN A CIRCLE
(1992-02-14)
CHANG, RC
;
LEE, HS
;
資訊工程學系
;
Department of Computer Science
In this note we propose an O(nm) algorithm for finding a maximum independent set of m chords which are incident to , vertices on a circle. This result can be applied to improving the time complexity of the algorithm for partitioning simple polygons into a minimum number of uniformly monotone polygons.
ON HITTING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES
(1991)
LEE, HS
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a dosed region bounded by a convex polygon P with n vertices such that no grid points in a plane fall between two adjacent lines of these parallel lines and size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + logm) approximation algorithm which guarantees finite performance ratio.