Logo

Login | Create Account

Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps

Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander (2004) Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. [Conference Paper]

Full text not available from this repository.

Abstract

In this paper, we present boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the points. Then we connect each label to its point such that no two connections intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. This work has partially been supported by the DFG grants Ka 512/8-2 and WO 758/4-1, by the German-Greek cooperation program GRC 01/048 and the EPEAEK program Pythagoras 89181(28).

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.630 Labeling
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:572
Deposited By:Selbach, Anna
Deposited On:19 Jul 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=49

Repository Staff Only: item control page

References

1. P. K. Agarwal, A. Effrat, and M. Sharir. Vertical decomposing of shallow levels in 3-dimensional arrangements and its applications. In Proc. 11th ACM Symp. Comp. Geom. (SoCG'95), pages 39-50, 1995.

2. M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Technical Report 2004-15, Fakultät für Informatik, Universität Karlsrughe, 2004. Available at http:/www.ubka. uni-karlsruhe.de/cgi-bin/psview?documnet=/ira/2004/15.

3.B. Chazelle and 36 co-authors. The computational geometry impact task force report. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, vol. 223, pp. 407-463. AMS 1999.

4. J.-D. Fekete and C. Plaisant. Excentric labeling: Dynamic neighborhood labeling for data visualization. In Proc. Conference on Human Factors in Computer Systems (CHI'99), pages 512-519, 1999.ACM New York.

5. M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. 7th ACM Symp. Comp. Geom. (SoCG'91), pages 281-288, 1991.

6. H. Freeman, S. Marrinan, and H. Chitalia. Automated labeling of soil survey maps. In Proc. ASPRS-ACM Annual Convention, Baltimore, vol. 1, pp. 51-59, 1996.

7. M. R. Garey and D. S. Johnson. Computers and Intractability: A Giúide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.

8. J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249-267, 1992.

9. C. Iturriaga. Map Labeling Problems. PhD thesis, University of Waterloo, 1999.

10. C. Iturriaga and A. Lubiw. Elastic labels around the perimeter of a map. Journal of Algorithms, 47(1):14-39, 2003.

11. G. W. Klau and P. Mutzel. Automatic layout and labelling of state diagrams. In W. Jäger and H.-J. Krebs, editors, Mathematics - Key Technology for the Future, pages 584-608. Springer-Verlag, Berlin, 2003.

12. T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. B. G. Teubner, 1990.

13. P. M. Vaidya. Geometry helps in matching. SIAM J. Comput., 18:1201-1225, 1989.

14. A. Wolff and T. Strijk. The Map-Labeling Bibliography. http://111www.ira.uka.de/map-labeling/bibliography/, 1996.

15. S. Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228-238, 1997.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.