论文标题
多边形中最大的三角形
Largest triangles in a polygon
论文作者
论文摘要
我们研究了可以在平面中的多边形中刻有最大区域三角形的问题。我们考虑了八种问题：我们使用凸多边形或简单多边形作为容器；我们要求三角形具有一个固定角度或所有三个角的角落。我们要么允许重新定位三角形，要么要求将其方向固定。我们为所有版本的所有版本提供了精确的算法。在具有$ n $顶点的凸多边形的重新定位的情况下，我们还会提出$（1- \ varepsilon）$近似算法。
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.
