## Labeling Points with Rectangles of Various Shapes
Nakano, Shin-Ichi and Nishizeki, Takao and Tokuyama, Takeshi and Watanabe, Shuhei
(2001)
Full text not available from this repository. ## AbstractWe deal with a map-labeling problem, named LOFL (Left-part Ordered Flexible Labeling), to label a set of points in a plane with 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 $\sigma$ 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 number of edges of polygonal obstacles.
Repository Staff Only: item control page References |