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

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

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

• 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
• scientific article; zbMATH DE number 4098718 (Why is no real title available?)
• scientific article; zbMATH DE number 1182912 (Why is no real title available?)
• 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

(28)

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

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)