Abstract
We deal with a map-labeling problem, named LOFL (Leftpart 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 σ 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 number of edges of polygonal obstacles.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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. Ajtai, 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 objects 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 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 serial 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 heuristics for point-feature cartographical label placement, GeoInformatica (2000) (also see http://www.lac.inpe.br/~lorena/missae/index.html)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nakano, Si., Nishizeki, T., Tokuyama, T., Watanabe, S. (2001). Labeling Points with Rectangles of Various Shapes. In: Marks, J. (eds) Graph Drawing. GD 2000. Lecture Notes in Computer Science, vol 1984. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44541-2_9
Download citation
DOI: https://doi.org/10.1007/3-540-44541-2_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41554-1
Online ISBN: 978-3-540-44541-8
eBook Packages: Springer Book Archive