TY - JOUR

T1 - Labeling points with rectangles of various shapes

AU - Koike, Atsushi

AU - Nakano, Shin Ichi

AU - Nishizeki, Takao

AU - Tokuyama, Takeshi

AU - Watanabe, Shuhei

PY - 2002/12

Y1 - 2002/12

N2 - 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 σ 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 σ, and an O((n + m) log2(n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the total number of edges of the polygonal obstacles.

AB - 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 σ 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 σ, and an O((n + m) log2(n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the total number of edges of the polygonal obstacles.

KW - Geographic information systems

KW - Map labelling

KW - Parametric search

KW - Plane sweep algorithm

UR - http://www.scopus.com/inward/record.url?scp=0036970559&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036970559&partnerID=8YFLogxK

U2 - 10.1142/S0218195902001018

DO - 10.1142/S0218195902001018

M3 - Article

AN - SCOPUS:0036970559

SN - 0218-1959

VL - 12

SP - 511

EP - 528

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 6

ER -