Approximating the maximum overlap of polygons under translation

DOI10.1007/S00453-016-0152-9MaRDI QIDQ527417zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled, Subhro Roy

Publication date 11 May 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.5778

zbMATH Keywords

approximation algorithmscomputational geometrypolygon overlap

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: 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(cn)$ 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.

Recommendations

• Approximating the maximum overlap of polygons under translation
• Computing the maximum overlap of two convex polygons under translations
• Shape matching under rigid motion
• Computing the maximum overlap of two convex polygons under translations
• Maximum overlap of convex polytopes under translation

Cites work

• Algorithm Theory - SWAT 2004
• Approximating the maximum overlap of polygons under translation
• Computing the maximum overlap of two convex polygons under translations
• Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
• Extremal polygon containment problems
• Finding a guard that sees most and a shop that sells most
• Geometric approximation algorithms
• Geometric optimization and sums of algebraic functions
• scientific article; zbMATH DE number 1424291 (Why is no real title available?)
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Matching convex shapes with respect to the symmetric difference
• Maximizing the overlap of two planar convex sets under rigid motions
• Maximum overlap of convex polytopes under translation
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Overlap of convex polytopes under rigid motion
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Shape matching under rigid motion
• Sublinear Geometric Algorithms
• Taking a walk in a planar arrangement

Cited in

(14)

• Computing the maximum overlap of two convex polygons under translations
• Improved upper bounds in the moving sofa problem
• Maximum overlap of convex polytopes under translation
• Approximating a planar convex set using a sparse grid
• Maximum overlap and minimum convex hull of two convex polyhedra under translations
• Matching sets of line segments
• Approximating the maximum overlap of polygons under translation
• Overlap of convex polytopes under rigid motion
• Maximizing the area of overlap of two unions of disks under rigid motion
• Placing Text Boxes on Graphs
• Algorithm Theory - SWAT 2004
• Computing the maximum overlap of two convex polygons under translations
• The maximum cover with rotating field of view
• A linear time algorithm for the maximum overlap of two convex polygons under translation

This page was built for publication: Approximating the maximum overlap of polygons under translation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527417)