Finding largest rectangles in convex polygons

DOI10.1016/J.COMGEO.2015.08.001MaRDI QIDQ902427zbMATH OpenOpenAlexFDO

Authors S. Cabello, Christian Knauer, Lena Schlipf, Otfried Cheong

Publication date 18 January 2016

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmconvex polygongeometric optimizationinscribed rectangle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Abstract: We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with $n$ vertices. We give exact algorithms that solve these problems in time $O(n^3)$. We also give $(1-varepsilon)$-approximation algorithms that take time $O(varepsilo{n}^{-3/2}+varepsilo{n}^{-1/2}logn)$.

Recommendations

• Maximum-area and maximum-perimeter rectangles in polygons
• Largest inscribed rectangles in convex polygons
• Finding the largest area axis-parallel rectangle in a polygon
• scientific article; zbMATH DE number 177850
• Peeling potatoes near-optimally in near-linear time

Cites work

• scientific article; zbMATH DE number 4098718 (Why is no real title available?)
• scientific article; zbMATH DE number 1182912 (Why is no real title available?)
• An optimal convex hull algorithm in any fixed dimension
• Approximation of convex bodies by rectangles
• Finding large sticks and potatoes in polygons
• Finding the largest area axis-parallel rectangle in a polygon
• Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets
• Largest inscribed rectangles in convex polygons
• The maximum numbers of faces of a convex polytope

Cited in

(26)

• Finding a largest-area triangle in a terrain in near-linear time
• Maximum-area and maximum-perimeter rectangles in polygons
• Finding a largest-area triangle in a terrain in near-linear time
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• scientific article; zbMATH DE number 4033105 (Why is no real title available?)
• Peeling potatoes near-optimally in near-linear time
• Largest placement of one convex polygon inside another
• A polynomial solution for the Potato-peeling problem
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Largest triangles in a polygon
• Finding a largest rectangle inside a digital object and rectangularization
• Isometric and affine copies of a set in volumetric Helly results
• Finding the largest area rectangle of arbitrary orientation in a closed contour
• scientific article; zbMATH DE number 522850 (Why is no real title available?)
• Largest triangle inside a terrain
• Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets
• Using symbolic calculations to determine largest small polygons
• Computing and Combinatorics
• Largest inscribed rectangles in convex polygons
• Some aperture-angle optimization problems
• Largest unit rectangles inscribed in a convex polygon
• Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
• Peeling potatoes near-optimally in near-linear time
• Extremal convex polygons inscribed in a given convex polygon
• Efficient algorithms for the largest rectangle problem
• Volume maximization and orthoconvex approximation of orthogons

This page was built for publication: Finding largest rectangles in convex polygons

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