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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/914

Actions (login required)

View Item View Item