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 , pp. 91-102(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_9).

Full text not available from this repository.

Abstract

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.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-44541-2_9
Classifications:	G Algorithms and Complexity > G.630 Labeling
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/307

Actions (login required)

View Item