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.

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
ID Code:307

Repository Staff Only: item control page

References

P. Agarwal, M. van Kreveld, and S. Suri, Label placement by maximum independent set in rectangles, Computational Geometry, Theory and Applications, 11 (1998) 209-218.

M. Ajitai, J. Komlos, and E. Szemeredi, Sorting in c log(n) parallel steps, Combinatorica, 3 (1983), pp. 1-19.

H. Aonuma, H. Imai, K. Imai, and T. Tokuyama, Maximin locations of convex objets in a polygon and related dynamic Voronoi diagrams, Proc. 6th ACM Symp. on Computational Geometry (1990) 225-234.

R. Cole, Slowing down sorting network to obtain faster sorting algorithms, J. ACM, 34 (1987) 200-208.

M. Formann and F. Wagner, A packing problem with applications to lettering of maps, Proc. 7th ACM Symp. on Computational Geometry (1991) 281-290.

C. Iturriaga and A. Lubiw, Elastic labels around the perimeter of a map, Proc. WADS'99 (1999) 306-317

K. Kakoulis and I. Tollis, A unified approach to a labeling graphical features, Proc. 14th ACM Symp. on Computational Geometry (1998) 347-356.

K. Kato, Studies on the Geometric Location Problems, L1 Approximation and Character Placing, Master Thesis, Kyushu University (February 1989).

M. van Kreveld, T. Strijk, and A. Wolff, Point set labeling with sliding labels, Computational Geometry, Theory and Applications, 13 (1999) 21-47.

N. Megiddo, Applying parallel computation algorithms in the design of seriel algorithms, J. ACM, 30 (1983) 852-865.

K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, ETACS Monograph 1, Springer Verlag, 1984.

J. Salowe, Parametric search, Section 37 of Handbook of Discrete and Computational Geometry, 683-695, (ed. J. Goodman and R. Polack), (1997) CRC Press.

I. Shamos and F. Preparata, Computational Geometry - An Introduction, Springer Verlag, 1985.

F. Wagner and A. Wolff, A practical map labeling heuristics algorithm Computational Geometry, Theory and Applications, 7 (1997) 387-404.

F. Wagner and A. Wolff, A combinatorial framework for map labeling, Proc. Graph Drawing '98, LNCS 1547 (1998) 316-331.

M. Yamamoto, G. Camara, L. Lorena, Tabu search heuristic for point feature cartographical label placement, GeoInformatica (2000) (also see http://www.lac.inpe.br/~lorena/missae/index.html)