Labeling Points with Rectangles of Various Shapes
Nakano, Shin-Ichi and Nishizeki, Takao and Tokuyama, Takeshi and Watanabe, Shuhei (2001) Labeling Points with Rectangles of Various Shapes. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 91-102 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_9).
Full text not available from this repository.
We 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