Back to Search
Start Over
LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES.
- Source :
-
International Journal of Computational Geometry & Applications . Dec2002, Vol. 12 Issue 6, p511. 18p. - Publication Year :
- 2002
-
Abstract
- We deal with a map-labeling problem, named LOFL (Left-part Ordered Flexible Labeling), to label a set of points in a plane in the presence of 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) log² (n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the total number of edges of the polygonal obstacles. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GEOMETRY
*POLYGONS
*RECTANGLES
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 12
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 8989754
- Full Text :
- https://doi.org/10.1142/S0218195902001018