Placing Text Boxes on Graphs: A Fast Approximation Algorithm for Maximizing Overlap of a Square and a Simple Polygonvan 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 , pp. 284295(Official URL: http://dx.doi.org/10.1007/9783642002199_27). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_27
AbstractIn 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.
Actions (login required)
