# Approximating the Maximum Overlap of Polygons under Translation

arXiv: https://arxiv.org/abs/1406.5778 · HTML: https://mlsanity.com/paper/1406.5778/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2014.

## Built on by (most cited first, 1 of 1)

- [The Maximum Cover with Rotating Field of View](https://mlsanity.com/paper/2309.15573/) (2023)

## Abstract (arXiv)

Let P and Q be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present an (1-varepsilon)-approximation algorithm, for finding the translation of Q, which maximizes its area of overlap with P. Our algorithm runs in O(c n) time, where c is a constant that depends only on k and varepsilon. This suggest that for polygons that are "close" to being convex, the problem can be solved (approximately), in near linear time.