Placing Text Boxes on Graphs: A Fast Approximation Algorithm for Maximizing Overlap of a Square and a Simple Polygon

Van Kreveld, Marc and Van Hagen, Sjoerd (2009) Placing Text Boxes on Graphs: A Fast Approximation Algorithm for Maximizing Overlap of a Square and a Simple Polygon. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, September 21- 24, 2008 , pp. 284-295 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_27).

Full text not available from this repository.

Abstract

In this paper we consider the problem of placing a unit square on a face of a drawn graph bounded by n vertices such that the area of overlap is maximized. Exact algorithms are known that solve this problem in O(n2 ) time. We present an approximation algorithm that— for any given ǫ > 0—places a (1 + ǫ)-square on the face such that the area of overlap is at least the area of overlap of a unit square in an optimal placement. The algorithm runs in O( 1 n log2 n) time. Extensions of the ǫ / √ algorithm solve the problem for unit discs, using O( log(1ǫ ǫ) n log2 n) time, ǫ and for bounded aspect ratio rectangles of unit area, using O( ǫ1 n log2 n) 2 time.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_27
Classifications:G Algorithms and Complexity > G.560 Geometry
ID Code:914

Repository Staff Only: item control page

References

Baker, B., Fortune, S., Mahaney, S.: Polygon containment under translation. J. Algorithms 7(4), 532–548 (1986)

de Berg, M., Cheong, O., Devillers, O., van Kreveld, M., Teillaud, M.: Computing the maximum overlap of two convex polygons under translations. Theory Comput. Syst. 31(5), 613–628 (1998)

de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry – Algorithms and Aplications. Springer, Berlin, 3rd edn. (2008)

Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M.: Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica 11(2), 116–132 (1994)

Daniels, K., Milenkovic, V., Roth, D.: Finding the largest area axis-parallel rectangle in a polygon. Comput. Geom. Theory Appl. 7, 125–148 (1997)

Dogrusöz, U., Feng, Q.W., Madden, B., Doorley, M., Frick, A.: Graph visualization o toolkits. IEEE Computer Graphics and Appl. 22(1), 30–37 (2002)

Dogrusöz, U., Kakoulis, K., Madden, B., Tollis, I.: On labeling in graph visualization. Inf. Sci. 177(12), 2459–2472 (2007)

Efrat, A., Sharir, M.: On the complexity of the union of fat convex objects in the plane. Discr. & Comput. Geometry 23(2), 171–189 (2000)

Gudmundsson, J., van Kreveld, M., Speckmann, B.: Efficient detection of patterns in 2D trajectories of moving points. GeoInformatica 11, 195–215 (2007)

Har-Peled, S., Mazumdar, S.: Fast algorithms for computing the smallest kenclosing circle. Algorithmica 41(3), 147–157 (2005)

Hoffman, K., Mehlhorn, K., Rosenstiehl, P., Tarjan, R.: Sorting jordan sequences in linear time using level-linked search trees. Information and Control 68(1–3), 170–184 (1986)

Iturriaga, C., Lubiw, A.: Elastic labels: the two-axis case. In: GD ’97. LNCS, vol. 1353, pp. 181–192 (1997)

Iturriaga, C., Lubiw, A.: Elastic labels around the perimeter of a map. J. Algorithms 47(1), 14–39 (2003)

Kakoulis, K., Tollis, I.: A unified approach to automatic label placement. Int. J. Comput. Geometry Appl. 13(1), 23–60

(2003)

van Kreveld, M.: On fat partitioning, fat covering, and the union size of polygons. Comput. Geom. Theory Appl. 9, 197–210 (1998)

van Kreveld,M., Schramm, E., Wolff, A.: Algorithms for the placement of diagrams on maps. In: GIS ’04: Proc. 12th annu. ACM Int. Symp. on Advances in Geographic Information Systems. pp. 222–231 (2004)

Mount, D., Silverman, R., Wu, A.: On the area of overlap of translated polygons. Computer Vision and Image Understanding 64(1), 53–61 (1996)

Paterson, M., Yao, F.: Binary partitions with applications to hidden surface removal and solid modelling. In: Proc. 5th annu. ACM Symp. on Computational Geometry. pp. 23–32 (1989)

Ryall, K., Marks, J., Shieber, S.: An interactive system for drawing graphs. In: GD ’96. LNCS, vol. 1190, pp. 387–394, Springer, Heidelberg (1997)

van der Stappen, A.: Motion Planning amidst Fat Obstacles. Ph.D. thesis, Department of Computer Science, Utrecht University (1994)

Veltkamp, R., Hagedoorn, M.: State of the art in shape matching. In: Lew, M. (ed.) Principles of Visual Information Retrieval, pp. 87–119. Springer (2000)