Skip Navigation



The Computer Journal Advance Access published online on September 11, 2009
The Computer Journal, doi:10.1093/comjnl/bxp087
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bekos, M. A.
Right arrow Articles by Symvonis, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2009. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Area-Feature Boundary Labeling1

Michael A. Bekos1, Michael Kaufmann2, Katerina Potika1 and Antonios Symvonis1,*

1 School of Applied Mathematical &Physical Sciences, National Technical University of Athens, 15780 Zografou, Athens, Greece
2 Institute for Informatics, University of Tübingen, Sand 13, 72076 Tübingen, Germany

* Corresponding author: symvonis{at}math.ntua.gr

Received 12 January 2008; revised 11 June 2009

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical drawings, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site s is associated with an axis-parallel rectangular label ls. The labels must be placed in distinct positions on the boundary of R and they must be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can ‘float’ within a polygonal region. We present a polynomial time algorithm, which runs in O(n3) time and produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of rectangle R.

Key Words: boundary labeling • map labeling • design and analysis of algorithms

Handling editor: Suchi Bhandarkar

1 This article is based on the preliminary version


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.