求凸多边形的最大面积多边形的算法外文翻译资料

本科毕业设计（论文）

外文翻译

求凸多边形的最大面积多边形的算法

作者：Markus Ausserhofer a,Susanna Dann b,Zsolt Langi c ，Geza Toth d,e

国籍：奥地利

出处：离散应用数学255 (2019)98-108

1. 介绍

长期以来，人们研究了在具有某些极值性质的几何约束下求凸多边形的算法问题.我们只列举了几个例子.博伊斯等人的[6]处理的问题，寻找最大面积或周长凸k-gons与顶点在给定的集合n点在平面上.Eppstein等人提出了一种算法，该算法在平面上给定n个点的集合中寻找具有顶点的最小面积凸k-gons.最小面积三角形[10,13,5]或更一般的凸k-gons[7,2]，用k lt; n来包围一个凸n-gon，在几篇论文中进行了研究.其他变量，即面积被另一个几何量所取代，也被研究，如[11].研究了给定简单多边形的最大面积凸多边形，如[3,12].在[5]中给出了在两个给定凸多边形之间寻找顶点数最少的多边形的算法.[14]的作者研究了将凸多边形的最大同伦副本放在另一个凸多边形中的问题.有关几何相关算法问题的更多信息，请参见[1].

定义1.让Psub;R2是一个凸n角.如果Q是一个包含P的凸多边形，且P的每个顶点都在Q的边界上，那么我们说Q是关于P的外切.集

A(P) = sup{area(Q): Q以P}为界，

如果它的存在.如果面积(Q) = A(P)且Q围绕P作界，则Q为围绕P作界的最大面积多边形.

注意，一个围绕P的多边形的任意边最多包含P的两个顶点，因此，它至少有n条边.这样的多边形可以有任意多条不包含P顶点的边.然而，不难看出，如果Q是一个以P为边界的最大面积多边形，那么Q的每条边至少包含P的一个顶点，因此它最多有n条边.此外,(P)是有限的,当且仅当P的任何两个连续的角的总和大于pi;.的确，如果这个性质成立，那么任意一个以P为边界的多边形的面积都小于P的面积和以P的三条连续边为边界的所有三角形的面积之和.另一方面,如果P连续有两个角的总和最多pi;,还有点任意远离P这样conv (Pcup;{q})是一个凸gon (n 1).因为这个多边形是以P为边界的它可以有任意大的面积，在这种情况下A(P) =infin;.特别地，这意味着如果A(P) lt;infin;，那么P至少有5个顶点.此外，如果Q是一个围绕凸多边形P的最大面积多边形，那么Q的每条边至少包含P的一个顶点.下面我们假设这些性质成立.

给定任意一个凸多边形P，我们的目标是找到一个关于P的最大凸多边形面积.研究了这些多边形的性质，并提出了一种求解算法.我们的结果可以用来约束一个正凸函数的积分.作为一个应用，我们限定了洛伦兹曲线的一个积分，并反驳了统计学中法里斯关于基尼指数的一个猜想.

本文的结构如下:在第二节中，我们建立了关于凸n-多边形的最大面积多边形的一些几何性质.在第3节中，我们提出了一种运行时间为O(n3)的算法，它可以找到一个(P)和围绕P边界的最大面积多边形.假设Q是关于P的.设S1，.Sn是P的逆时针方向的边.如果Si在Q的边界上，我们说Si被Q“使用”，如果Si在Q的边界上，我们说Si被Q“使用”，如果Si在Q的边界上，我们说Si被Q“使用”，如果Si在Q的边界上，我们说Si没有被Q使用.我们可以将一个序列从{U,N} N赋值到Q，这样，如果使用Si，第i项就是U，否则就是N.在第四节中，我们研究了以下问题:对于某些P.我们没有一个完整的表征，只有部分结果.在第5节中，我们描述了我们的方法在统计中的应用，并反驳了在[9]中Farris的猜想.最后，在第6节中，我们收集我们的补充意见，并提出一些有待解决的问题.

在这篇文章中,Psub;R2表示一个凸n角,nge;5,任何两个连续的角度的P的总和大于pi;.P的顶点用p1 p2hellip;， pn，逆时针方向.我们把下标推广到所有整数上这样下标就可以对n取余;也就是说，我们令pi = pj如果ine;j mod n.对于任何i，我们用Si表示P的边pi 1.用Ti表示以Si为界的三角形以及通过Si - 1和Si 1的直线;它被称为第i个外部三角形.显然，如果Q是关于P的，那么Q的每个顶点都在P的外三角形中.注意，如果Q的三个连续顶点位于同一条直线上，那么移除中间的顶点并不会改变Q的面积.因此,不失一般性,在我们的调查,我们只处理外切多边形没有一个角等于pi;.这特别意味着，如果使用了P的一条边(即包含在被外切多边形Q的边界中)，那么它就包含在Q的一条边中.我们表示的边界Q bd (Q),以及任何点pisin;R2和集合Ssub;R2,我们称之为S对p的旋转复制pi;年代的反射p.

2. 最大面积外切多边形的几何性质

定理1.对于任意i, j, ile;kle;i n，设Q为一个凸多边形，其最大面积为P，其中Sk, Sk 1，hellip;，其边界Si n:即P的这些边被Q使用.那么对于每一个j = i 2 i 3hellip;k - 1

(a) pj是包含它的Q的边的中点，或者

(b) Sj - 1或Sj位于bd(Q)上.

证明.假设Sj - 1和Sj都不在bd(Q)上.这清楚地表明pj恰好属于Q的一边，我们用V表示它.我们证明在这种情况下pj是V的中点.让V (分别地.V -)是Q的边，紧接着(resp).令q = Vcap;V ， q - = Vcap;Vminus;，令L, L ， Lminus;分别为贯穿V, V ， Vminus;的直线.假设pk不是V的中点.我们可以在不失一般性的前提下假定|pjq | gt; |pkq - |.L对pk旋转顺时针方向的一个很小的角alpha;,表示结果逐L′与L 和L的交叉minus;问′ 和q′minus;,分别.设T 是由L L 决定的三角形，设T -是由L决定的三角形

minus;

我，还有我.自| pjq | gt; | pjqminus;|,区域(T ) = | | pjq alpha; O(alpha;2)和地区(Tminus;) = | pjqminus;|alpha; O(alpha;2).因此,如果alpha;是非常小的,那么面积(T ) gt; (Tminus;).另一个可能的理由是,既然| pjq | gt; | pjqminus;|和alpha;很小,我们有| pjq′ | gt; | pjq′minus;|,暗示对pk包含T T的反射minus;(cf无花果.1).因此修改问代替L, L′将增加它的面积.这意味着如果Q的面积最大，那么pj就是V的中点.

备注1.使用同样的证明，很明显，定理1也适用于任何不限制使用P的任何边的最大面积多边形Q.

定义2.令1le;kle;n，令q0, q1，hellip;， qk为平面上的点.我们说多边形曲线C = q0q1···qk满足指数i的中点性质，如果j = 1,2，hellip;(k) P的顶点( j)是qj - 1qj的中点.

如果k = n, q0 = qk，即C是一条闭合多边形曲线，它满足某个指数i的中点性质，那么我们说C满足中点性质.

定理2.我们有以下产品:

(2.1)如果n为奇数，则恰好有一条满足中点性质的闭合多边形曲线.

(2.2)如果n是偶数,sum;n k = 1(minus;1)肃贪会̸= 0,那么就没有封闭多边形曲线满足中点的财产.

One hundred. M. Ausserhofer, S. Dann, Z. Langi等/离散应用数学255 (2019)98-108

图1所示.用L 替换L 会增加Q的面积.

(2.3)如果n是偶数，sum;n k=1(- 1)kpk = 0，则对于每一个qisin;R2，恰好有一条满足中点性质的闭合多边形曲线C，使得q是包含p1和pn的C两边的公共端点.此外，C的带符号面积的绝对值与q无关.

证明.设C = q0q1···qn, q0 = qn为满足指数0的中点性质的闭合多边形曲线.对于每一个k, qk是qk - 1关于pk的反射，因此设q:= q0，我们有q1 = 2p1 - q, q2 = 2p2 - 2p1 q，或者一般来说qk = 2

sum;k

j = 1 (minus;1) kminus;jpj (minus;1) kq.特别地，由于C是闭的，我们得到q = 2

sum;n

k = 1 (minus;1) nminus;kpk nq (minus;1).如果n是奇数

因此q =

sum;n

k = 1 (minus;1) nminus;肃贪会证明(2.1).如果n是偶数，它是这样的

sum;n

k = 1 (minus;1) nminus;肃贪会=

sum;n

k=1(- 1)kpk = 0，表示(2.2)和(2.3)的第一部分.接下来，我们证明C的有符号区域，也用面积(C)表示，与q无关.对于任意u visin;R2，我们用|u v|表示

以u和v为列向量的2times;2矩阵的行列式.因为对于每k， |qk - 1, qk| = |qk - 1, qk - 1 qk| = 2|qk - 1, pk|，我们得到

面积(C) = 1 2

nsum;

k = 1

| qkminus;1, qk | =

nsum;

k = 1

| qkminus;1, pk | =

nsum;

k = 1

⏐⏐⏐⏐⏐⏐

2

kminus;1sum;j = 1

(- 1)k - 1 - jpj (- 1)k - 1q, pk

⏐⏐⏐⏐⏐⏐

.

对于某个函数f = f (p1, p2，hellip;面积(C) = f (p1, p2，hellip;pn)

nsum;

k = 1

|(- 1)k - 1q, pk| = f (p1, p2，hellip;pn)minus;

⏐⏐⏐⏐⏐

问,

nsum;

k = 1

(minus;1)肃贪会

⏐⏐⏐⏐⏐

,

哪个独立于q，因为

sum;n

k = 1(minus;1)肃贪会= 0.

定理的下列变体也可以被证明.我们省略了这个证明，因为它是基于与定理2完全相同的计算.

定理3.设1le;k lt; n - 1.设C为满足指数i中点性质的多边形曲线族C = q0q1···qk，其中q0在直线Li - 1至Si - 1上，qk在直线Li k 1至Si k 1上.

(3.1)如果Li - 1和Li k 1不平行，则C恰好有一个元素.(3.2)如果李minus;1和李 k 1是平行的和李 k 1̸= 2

sum;k

j=1(- 1)k - jpi j (- 1)kLi - 1，则C =empty;.

(3.3)如果Li - 1与Li k 1平行且Li k 1 = 2

sum;k

j=1(- 1)k - jpi j (- 1)kLi - 1，那么对于每一个q0isin;Li - 1，就恰好有一个

多边形曲线Cisin;C，从q0开始.此外，由- 1q0cup;Ccup;qk， k 2cup;所围的带符号区域

(⋃n kminus;2

j =我 k 2 Sj

)

与q0的选择无关.备注2.

bull;通过计算q =sum;n k=1(- 1)n - kpk，可以在O(n)时间内找到(2.1)中唯一的起始点q.计算解C，检查它的凸性，计算它的面积，都需要同样的时间.

bull;(2.3)对于所有可能的起始点q的区域，可以找到一个凸解，步骤为inO(n log n).事实上，满足中点性质的多边形曲线是凸的，当且仅当每个顶点位于对应的外部三角形Ti (P)中时.每一个条件都给出了起点q上的三个线性约束条件，这些约束条件可以在O(n)步中得到，并且这3n个半平面的交集可以在O(n log n)时间[4]中计算出来.

M. Ausserhofer, S. Dann, Z. Langi等/离散应用数学255 (2019)98-108 101

bull;如果(2.3)中存在凸解Q，则存在一个包含P的边的凸解Q.的确，如果q在可行域的边界上，那么对于某些j, qj位于P的一条边线上，这就得到q包含P的一条边.

bull;在(3.1)中唯一的起始点q0，对应的解C = q0q1hellip;利用q0是Li - 1与2的交点这一事实，qk的凸性性质及其面积可在O(k)步中找到 剩余内容已隐藏，支付完成后下载完整资料

---

Discrete Applied Mathematics 255 (2019) 98–108

Contents lists available at ScienceDirect

Discrete Applied Mathematics

journal homepage: www.elsevier.com/locate/dam

An algorithm to find maximum area polygons circumscribed about a convex polygon

Markus Ausserhofer a, Susanna Dann b, Zsolt Laacute;ngi c,lowast;, Geacute;za Toacute;th d,e

a University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria

b Departamento de Matematicas, Universidad de los Andes, Carrera 1 No 18A 12 , 111711 Bogotaacute;, Colombia

c Research Group of Morphodynamics, Hungarian Academy of Sciences and Department of Geometry, Budapest University of Technology and Economics, Egry Joacute;zsef u. 1., 1111 Budapest, Hungary

d Reacute;nyi Institute of Mathematics, Hungarian Academy of Sciences, Reaacute;ltanoda u. 13-15, 1053 Budapest, Hungary

e Department of Comp. Sci. and Inf. Theory, Budapest University of Technology, Magyar tudoacute;sok kouml;ruacute;tja 2, 1117, Budapest, Hungary

a r t i c l e i n f o a b s t r a c t

Article history:

Received 25 June 2017

Received in revised form 10 July 2018 Accepted 24 August 2018

Available online 11 October 2018 Keywords:

Circumscribed polygon Area

Gini index

A convex polygonQ is circumscribed about a convex polygon P if every vertex of P lies on at least one side of Q . We present an algorithm for finding a maximum area convex polygon circumscribed about any given convex n-gon in O(n3) time. As an application, we disprove a conjecture of Farris. Moreover, for the special case of regular n-gons we find an explicit solution.

copy; 2018 Elsevier B.V. All rights reserved.

1. Introduction

The algorithmic aspects of finding convex polygons under geometric constraints with some extremal property have been studied for a long time. We list just a few examples. Boyce et al. [6] dealt with the problem of finding maximum area or perimeter convex k-gons with vertices in a given set of n points in the plane. Eppstein et al. [8] presented an algorithm that finds minimum area convex k-gons with vertices in a given set of n points in the plane. Minimum area triangles [10,13,5] or more generally, convex k-gons [7,2], enclosing a convex n-gon with k lt; nwere studied in several papers. Other variants, where area is replaced by another geometric quantity, were also investigated, see e.g. [11]. Maximum area convex polygons in a given simple polygon were examined, e.g. in [3,12]. Algorithms to find polygons with a minimal number of vertices, nested between two given convex polygons, were presented in [5]. The authors of [14] examined among other questions the problem of placing the largest homothetic copy of a convex polygon in another convex polygon. For more information on geometry-related algorithmic questions, see [1].

Definition 1. Let P sub; R2 be a convex n-gon. If Q is a convex polygon that contains P and each vertex of P is on the boundary of Q , then we say that Q is circumscribed about P . Set

A(P) = sup{area(Q ) : Q circumscribed about P},

if it exists. If area(Q ) = A(P) and Q is circumscribed about P , then Q is amaximum area polygon circumscribed about P .

lowast; Corresponding author.

E-mail addresses: markus.ausserhofer@hotmail.com (M. Ausserhofer), s.dann@uniandes.edu.co (S. Dann), zlangi@math.bme.hu (Z. Laacute;ngi), toth.geza@renyi.mta.hu (G. Toacute;th).

https://doi.org/10.1016/j.dam.2018.08.017

0166-218X/copy; 2018 Elsevier B.V. All rights reserved.

M. Ausserhofer, S. Dann, Z. Laacute;ngi et al. / Discrete Applied Mathematics 255 (2019) 98–108 99

Note that any side of a polygonQ circumscribed about P contains atmost two vertices of P , and thus, it has at least n 2 sides. Such a polygon may have arbitrarily many sides that do not contain any vertex of P . Nevertheless, it is not hard to see that if Q is a maximum area polygon circumscribed about P , then every side of Q contains at least one vertex of P , and hence, it has at most n sides. Furthermore, A(P) is finite if and only if the sum of any two consecutive angles of P is greater than pi; . Indeed, if this property holds, then the area of any polygon circumscribed about P is less than the sum of the area of P and the areas of all triangles bounded by three consecutive sidelines of P . On the other hand, if P has two consecutive angles whose sum is at most pi; , then there is a point q arbitrarily far from P such that conv(P cup; {q}) is a convex (n 1)-gon. Since this polygon is circumscribed about P and it can have arbitrarily large area, in this case A(P) = infin;. In particular, thismeans that if A(P) lt; infin;, then P has at least five vertices. Furthermore, observe that if Q is a maximum area polygon circumscribed about a convex polygon P , then every side of Q contains at least one vertex of P . In the following we assume that these properties hold.

Given any convex polygon P , our aim is to find a maximum area convex polygon circumscribed about P . We investigate the properties of these polygons and present an algorithm to find them. Our results can be used to bound an integral of a positive convex function. As an application, we bound an integral of the Lorenz curve and disprove a conjecture of Farris about the Gini index in statistics.

This paper is organized as follows: In Section 2 we establish some geometric properties of maximum area polygons circumscribed about a convex n-gon. In Section 3 we present an algorithm with O(n3) running time that finds A(P) and the maximum area polygons circumscribed about P . Suppose that Q is circumscribed about P . Let S1, . . . , Sn be sides of P in counterclockwise order. We say that Si is lsquo;lsquo;usedrsquo;rsquo; by Q if it is on the boundary of Q , and lsquo;lsquo;not usedrsquo;rsquo;

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[271831]，资料为PDF文档或Word文档，PDF文档可免费转换为Word