Browsing by Author "Lee, D. T."

Now showing 1 - 2 of 2

Maximizing the number of independent labels in the plane
(2007)
Yu, Kuen-Lin
;
Liao, Chung-Shou
;
Lee, D. T.
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider a map labeling problem to maximize the number of independent labels in the plane. We first investigate the point labeling model that each label can be placed on a given set of anchors on a horizontal line. It is known that most of the map labeling decision models on a single line (horizontal or slope line) can be easily solved. However, the label number maximization models are more difficult (like 2SAT vs. MAX-2SAT). We present an O(n log Delta) time algorithm for the four position label model on a horizontal line based on dynamic programming and a particular analysis, where n is the number of the anchors and Delta is the maximum number of labels whose intersection is nonempty. As a contrast to Agarwal et al.'s result [Comput. Geom. Theory Appl. 11 (1998) 209-218] and Chan's result [Inform. Process. Letters 89(2004) 19-23] in which they provide (1 + 1/k)-factor PTAS algorithms that run in O(nlogn + n(2k-1)) time and O(n log n + n Delta(k-1) time respectively for the fixed-height rectangle label placement model in the plane, we extend our method to improve their algorithms and present a (1 + 1/k)-factor PTAS algorithm that runs in O(n log n+kn log(4) Delta + Delta (k-1)) time using O(k Delta log(4) + k Delta(k-1)) storage.
Time convex hull with a highway
(2007)
Yu, Teng-Kai
;
Lee, D. T.
;
資訊工程學系
;
Department of Computer Science
We consider the problem of computing the time convex hull of a set of points in the presence of a straight-line highway in the plane. The traveling speed in the plane is assumed to be much slower than that along the highway. The shortest time path between two arbitrary points is either the straight-line segment connecting these two points or a path that passes through the highway. The time convex hull, CHt(P), of a set P of n points is the smallest set containing P such that all the shortest time paths between any two points lie in CHt(P). In this paper we give a Theta(n log n) time algorithm for solving the time convex hull problem for a set of n points in the presence of a highway.