Abstract | ||
---|---|---|
We deal with a map-labeling problem, named LOFL (Left-part Ordered Flexible Labeling), to label a set of points in a plane in the presence of polygonal obstacles. The label for each point is selected from a set of rectangles with various shapes satisfying the left-part ordered property, and is placed near to the point after scaled by a scaling factor a which is common to all points. In this paper, we give an optimal O((n + m) log(n + m)) algorithm to decide the feasibility of LOFL for a fixed scaling factor sigma, and an O((n + m) log(2) (n + m)) time algorithm to find the largest feasible scaling factor sigma, where n is the number of points and m is the total number of edges of the polygonal obstacles. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1142/S0218195902001018 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | Field | DocType |
map labelling, geographic information systems, plane sweep algorithm, parametric search | Sorting network,Scale factor,Discrete mathematics,Polygon,Combinatorics,Search algorithm,Mathematics,Object point | Journal |
Volume | Issue | ISSN |
12 | 6 | 0218-1959 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Atsushi Koike | 1 | 58 | 17.02 |
Shin-ichi Nakano | 2 | 246 | 24.40 |
Takao Nishizeki | 3 | 1771 | 267.08 |
Takeshi Tokuyama | 4 | 1179 | 417.31 |
Shuhei Watanabe | 5 | 5 | 1.49 |