Largest triangles in a polygon

DOI10.1016/J.COMGEO.2021.101792MaRDI QIDQ2230417zbMATH OpenOpenAlexFDO

Authors Seungjun Lee, Taekang Eom, Hee-Kap Ahn

Publication date 17 September 2021

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

largest trianglemaximum-area trianglesimple polygon

Mathematics Subject Classification ID

Elementary problems in Euclidean geometries (51M04) Geometric constructions in real or complex geometry (51M15) Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: We study the problem of finding maximum-area triangles that can be inscribed in a polygon in the plane. We consider eight versions of the problem: we use either convex polygons or simple polygons as the container; we require the triangles to have either one corner with a fixed angle or all three corners with fixed angles; we either allow reorienting the triangle or require its orientation to be fixed. We present exact algorithms for all versions of the problem. In the case with reorientations for convex polygons with $n$ vertices, we also present $(1-varepsilon)$-approximation algorithms.

Review text

The authors consider the following problem: Suppose we are given a simple polygon \(P\) in the plane and a set \(\mathcal{S}\) of triangles, find a triangle \(T\) that has maximal area under the following constraints: \begin{itemize} \item \(T\) is inscribed in \(P\), and \item \(T\) is up to rotations, translations and scalings equivalent to a triangle in \(\mathcal{S}\). \end{itemize} The authors present an exact algorithm for computing \(T\), when \(\mathcal{S}\) consists of a single triangle. In addition, several variants of the above problem are investigated. For example, \begin{itemize} \item the container polygon~\(P\) is additionally assumed to be convex, \item the set~\(\mathcal{S}\) consists of a triangle and the reflection of this triangle, \item the set~\(\mathcal{S}\) consists of all triangles that have a corner with some fixed interior angle~\(\alpha\), and/or \item the area of \(T\) is not maximal, but only requires to be at least \((1-\varepsilon)\) times the maximal possible area for some given \(0<\varepsilon<1\). \end{itemize} The main results are presented in terms of time/space complexities. The problems are of interest in pattern recognition, computer vision and computational geometry.

Recommendations

• Largest triangle inside a terrain
• scientific article; zbMATH DE number 2169076
• Maximum-area triangle in a convex polygon, revisited
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Finding largest rectangles in convex polygons

Cites work

• A polynomial solution for the Potato-peeling problem
• Computing a maximum axis-aligned rectangle in a convex polygon
• Extremal polygon containment problems
• Finding large sticks and potatoes in polygons
• Finding largest rectangles in convex polygons
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 741008 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• scientific article; zbMATH DE number 7650309 (Why is no real title available?)
• Largest placement of one convex polygon inside another
• Maximizing the overlap of two planar convex sets under rigid motions
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• Simultaneous inner and outer approximation of shapes

Cited in

(17)

• Largest placement of one convex polygon inside another
• Largest and smallest area triangles on imprecise points
• Largest triangle inside a terrain
• Calabi triangles for regular polygons
• On the most robust affine basis
• Finding the largest area rectangle of arbitrary orientation in a closed contour
• Largest inscribed rectangles in convex polygons
• scientific article; zbMATH DE number 2169076 (Why is no real title available?)
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• Optimal Embedded and Enclosing Isosceles Triangles
• Largest area parallelogram inside a digital object in a triangular grid
• Largest unit rectangles inscribed in a convex polygon
• Fat triangles inscribed in arbitrary planar domains
• Largest similar copies of convex polygons in polygonal domains
• Convex polygon containment: improving quadratic to near linear time
• Maximum-area triangle in a convex polygon, revisited
• Finding a largest-area triangle in a terrain in near-linear time

This page was built for publication: Largest triangles in a polygon

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