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.
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.
Repository Staff Only: item control page