Special Issue: Selected Papers from Computational Geometry and Applications (CGA) Workshop, May 2006, Glasgow, UKNo Access

DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION

MARINA L. GAVRILOVA

MARINA L. GAVRILOVA

Department of Computer Science, University of Calgary, 2500 University Drive N.W., Calgary, AB, Canada, T2N1N4, Canada

Search for more papers by this author

https://doi.org/10.1142/S021819590900299XCited by:0 (Source: Crossref)

Abstract

Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing a map region P such that a rectangular axis-parallel label L of a given size can be placed in it. The map region to be labeled is in general a non-convex n-gon which may contain holes. We first derive a new practical algorithm based on the sweep-line technique that determines the com set of Maximum Inscribed Rectangles (MIRs) in P in O(nk), where k is the size of the output, for the case when the polygon sides have an axis-parallel orientation. After the set of MIRs has been found, any subsequent query on label L placement runs in only O(logn) time. We then provide an algorithm to convert the general case to the axis-parallel case. Extensive experimentation in both laboratory and industrial settings confirms that the developed method is practical and highly efficient for processing large GIS data sets.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

H. Alt, D. Hsu and J. Snoeyink, Computing the largest inscribed isothetic rectangle, Technical report, TR-94-28, University of British Columbia, Vancouver, BC, Canada (1994) . Google Scholar
P. K. Agarwal, M. van Kreveld and S. Suri, Comput. Geom.: Th. App. 11, 209 (1998), DOI: 10.1016/S0925-7721(98)00028-5. Crossref, Web of Science, Google Scholar
M. A. Bekoset al., Boundary labeling: Models and efficient algorithms for rectangular maps, Proc. 12th Int. Symp. Graph Drawing (GD'04), Lecture Notes in Computer Science, ed. J. Pach (Springer-Verlag) pp. 49–59. Google Scholar
P. Bermanet al., J. Algorithms 42(2), 443 (2001). Google Scholar
T. M. Chan, Inform. Process. Lett. 89(1), 19 (2004), DOI: 10.1016/j.ipl.2003.09.019. Crossref, Web of Science, Google Scholar
K. Daniels, V. Milenkovic and D. Roth, Comput. Geom. 7(1-2), 125 (1997), DOI: 10.1016/0925-7721(95)00041-0. Crossref, Web of Science, Google Scholar
U. Dogrusozet al., Inform. Sci. 177(12), 2459 (2007), DOI: 10.1016/j.ins.2007.01.019. Crossref, Web of Science, Google Scholar
U. I. Gupta, D. T. Lee and J. Y.-T. Leung, Networks 12, 459 (1982), DOI: 10.1002/net.3230120410. Crossref, Web of Science, Google Scholar
H. Imai and T. Asano, J. Algorithms 4, 310 (1983), DOI: 10.1016/0196-6774(83)90012-3. Crossref, Web of Science, Google Scholar
C. Iturriaga and A. Lubiw, J. Algorithms 47, 14 (2003), DOI: 10.1016/S0196-6774(03)00004-X. Crossref, Web of Science, Google Scholar
M. Jianget al., New bounds on map labeling with circular labels, Proc. 15th Ann. Int. Symp. Algorithms and Computation (ISAAC'04), Lecture Notes in Computer Science 3341, eds. R. Fleischer and G. Trippen (2004) pp. 606–617. Google Scholar
D. Levin and M. Sharir, Discr. Comput. Geom. 2, 9 (1987). Crossref, Web of Science, Google Scholar
S. Royet al., Inform. Proc. Lett. 89(2), 91 (2004), DOI: 10.1016/j.ipl.2003.10.002. Crossref, Web of Science, Google Scholar
M. van Kreveld, É. Schramm and A. Wolff, Algorithms for the placement of diagrams on maps, Proc. 12th Int. Symp. ACM GIS (GIS'04), eds. D. Pfoder, I. F. Cruz and M. Ronthaler pp. 222–231. Google Scholar
J. W. van Roessel, The American Cartographer 16(3), 201 (1989), DOI: 10.1559/152304089783814034. Crossref, Google Scholar
Q. Zhang and L. Harrie, Real-time map labelling for personal navigation, Proc. 12th Int. Conf. Geoinformatics (2004) pp. 39–46. Google Scholar
B. Zhu and C. K. Poon, Int. J. Comput. Geom. Appl. 11(4), 455 (2001), DOI: 10.1142/S0218195901000584. Link, Web of Science, Google Scholar

Vol. 19, No. 04

Metrics

Downloaded 31 times

History

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION

Abstract

Recommended