Extremal convex polygons inscribed in a given convex polygon

DOI10.1016/J.COMGEO.2021.101844MaRDI QIDQ2064020zbMATH OpenOpenAlexFDO

Authors Csenge Lili Ködmön, Zsolt Lángi

Publication date 3 January 2022

Published in Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

convex polygondual billiardminimum areaminimum perimeter

Mathematics Subject Classification ID

Dynamical systems of geometric origin and hyperbolicity (geodesic and horocycle flows, etc.) (37D40) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Analysis of algorithms and problem complexity (68Q25)

Abstract: A convex polygon $Q$ is inscribed in a convex polygon $P$ if every side of $P$ contains at least one vertex of $Q$. We present algorithms for finding a minimum area and a minimum perimeter convex polygon inscribed in any given convex $n$-gon in $O(n)$ and $O(n^3)$ time, respectively. We also investigate other variants of this problem.

Recommendations

• Maximum-area and maximum-perimeter rectangles in polygons
• Largest inscribed rectangles in convex polygons
• Minimum-perimeter enclosures
• Finding Extremal Polygons
• Finding largest rectangles in convex polygons

Cites work

• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• An algorithm to find maximum area polygons circumscribed about a convex polygon
• An efficient algorithm for determining the convex hull of a finite planar set
• An optimal algorithm for finding minimal enclosing triangles
• Duality of caustics in Minkowski billiards
• Elementary approach to closed billiard trajectories in asymmetric normed spaces
• Finding Extremal Polygons
• Finding minimum area \(k\)-gons
• Finding the smallest triangles containing a given convex polygon
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 2229974 (Why is no real title available?)
• On the existence of Fagnano trajectories in convex polygonal billiards
• Shortest billiard trajectories
• Shortest periodic billiard trajectories in convex bodies

Cited in

(12)

• An algorithm to find maximum area polygons circumscribed about a convex polygon
• On the maximum area of inscribed polygons
• Some inequalities between two polygons inscribed one in the other
• scientific article; zbMATH DE number 2186372 (Why is no real title available?)
• Finding Extremal Polygons
• scientific article; zbMATH DE number 5542497 (Why is no real title available?)
• scientific article; zbMATH DE number 3988128 (Why is no real title available?)
• Largest inscribed rectangles in convex polygons
• The circumpolygon with maximal area
• scientific article; zbMATH DE number 3103938 (Why is no real title available?)
• Minimal convex \(k\)-gons containing a given convex polygon
• Minimum-perimeter enclosures

This page was built for publication: Extremal convex polygons inscribed in a given convex polygon

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