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(n~2) 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 log~2 n) time. Extensions of the algorithm solve the problem for unit discs, using O((log(1/ε) ε{the square root of}ε n log~2 n) time, and for bounded aspect ratio rectangles of unit area, using O(1/ε~2 n log~2 n) time.
展开▼
