等周多边形面积最大问题

<正>设桌面上有一个由铁丝围成的封闭曲线,周长是2L.求证:当封闭曲线是n边形时,正n边形面积最大.(简称"等周多边形问题")分析与证明(1)当多边形为凹多边形时,通过轴对称,可以使其在周长不变的情况下面积变大,所以以下只需要证明凸多边形的情况.     

平面三次H-Bézier曲线的形状分析

本文对平面三次H-Bézier曲线的形状进行分析,讨论其诸如奇点、拐点、局部凸和全局凸的几何特征,得出曲线上含有奇点、拐点和曲线为局部凸或全局凸的用控制多边形边向量相对位置表示的充分必要条件.     

平面三次H-Bézier曲线的形状分析

本文对平面三次H-Bézier曲线的形状进行分析,讨论其诸如奇点、拐点、局部凸和全局凸的几何特征,得出曲线上含有奇点、拐点和曲线为局部凸或全局凸的用控制多边形边向量相对位置表示的充分必要条件.     

双圆封闭折线一类特例研究

杨之先生在其名著[1 ] 中倡导研究的“双圆多边形”是指既有外接圆又有内切圆的多边形 .仿此 ,我们给出下面的定义　若一条封闭折线的顶点都在一个圆上 ,每条边都与另一个圆相切 ,则称该折线为双圆封闭折线 .相应地 ,若它的边数为 n,环数为 k,则称为 n边 k环双圆封闭折线 .图 1     

欧拉凸多面形定理和欧拉示性数

Ⅰ.凸多面形的欧拉定理 1.定理的敍述和来源象中学立体几何教科书中所說的,由若干个平面多边形所围成的封閉的立体叫作多面体。这些多边形的每一个叫作多面体的面,这些多边形的边和頂点分別叫作多面体的棱和頂点。当多面体在它的每一个面的平面的同一側,它就叫作凸多面体。凸多面体的表面叫作凸多面形,它的面、棱和頂点也就是凸多面形的面、棱和頂点。例如图1中的(一)到(四)都是凸多面形,图1中的(五)不是凸多面形。     

四边形中的趣味竞赛题(上)

<正>在平面上由首尾相连的四条线段组成的封闭图形,叫做四边形.四边形可以分为凸四边形,凹四边形和交叉四边形.四边形具有四个顶点和四条边,我们一般研究凸四边形,也就是将每条边延长为直线后,其余各边都在这条边所在直线的一侧,四边形中没有公共顶点的两条边叫做对边,没有公共边的两个角叫做对角,对角顶点的连接线段叫做四边形的对角线.没有特别声明,今后     

复平面内任意多边形的面积公式

我们统称可凸可凹的平面多边形为任意多边形,并约定,沿任意多边形A1A2…An的边界行走一圈,如果图形总在行走者的左侧,则称此绕行方向为正向,多边形A1A2…An为正向多边形,正向n边形A1A2…An的面积记为SA1A2…An.文[1]给出了复数形式的正向△ABC的面积公式S△ABC=12Im〔(B-A)(C-A)〕1文[2]给出了复数形式的正向任意四边形ABCD的面积公式SABCD=12Im〔(A B-C-D)(B-D)〕2公式右边的大写字母A,B,C,D等既表示点,也表示这些点所对应的复数(下同).本文将给出复数形式的任意多边形的面积公式.1　两个面积公式的变形上述两个公式分别…     

平面C-Bézier曲线的奇拐点分析

本文完全地讨论了平面C-曲线和平面C-Bezier曲线的奇拐点和凸性性质:曲线段为且必为下列情形之一:有一各拐点,两个拐点,一个尖点,一个二重结点,处处为凸;并给出了相应的用控制多边形相对位置表示的充分必要条件.     

关于多边形分平面区域的计数问题

平面区域的计数问题是组合数学中的一个专题 .本文将利用递推函数的方法来讨论ｎ个开放图形或ｎ个封闭图形分平面所得到的最多区域数的问题 .首先给出封闭图形和开放图形的概念 :封闭图形 :指一般的凸ｎ边形 ;如 ,三角形、四边形 .开放图形 :指在凸ｎ边形中去掉ｍ条边 (ｎ-2 ≥ｍ≥ 1 ) ,如果可以把被去掉的边的端点在图中相关的线段改为射线或直线 ;如 ,一组平行线、角ＡＯＢ .其中每一条直线、线段或射线都称为边 .定理 1　ｎ个角 (这里只讨论锐角的情况 )最多把平面分成 2ｎ2 -ｎ +1个区域 .分析　当ｎ个角把平面分成的区域数最多时 ,这…     

由两点确定的具凸包性和保凸性的三次有理Bézier曲线

１．引言 在文［１］中,本文作者探讨了当控制多边形为凸时,过控制多边形内部任意给定两点的三次有理 Ｂéｚｉｅｒ曲线的存在唯一性问题,给出了这样的曲线存在的充要条件并证明了其若存在则是唯一的,还给出了其权因子的计算式．但由两点确定的三次有理 Ｂｚｉｅｒ曲线的权因子不一定非负,从而不能保证曲线具凸包性和保凸性,而无论从理论还是实用角度看,曲线的这两个性质都是很重要的． 本文从如下方面进一步深化［１］的论题：当凸控制多边形内部两点 ｐ１, ｐ２满足什么条件时,过Ｐ１,Ｐ２两点的三次有理 Ｂéｚｉｅｒ曲线不仅…     

Converting triangulations to quadrangulations

We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most n/3, and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most n/4 Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.     

Safety Zone Problem

Given a simple polygon P, its safety zone S (of width δ) is a closed region consisting of straight line segments and circular arcs (of radius δ) bounding the polygon P such that there exists no pair of points p (on the boundary of P) and q (on the boundary of S) having their Euclidean distance d(p, q) less than δ. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple polygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN) time, where M and N are the number of vertices of both the polygons.     

Inflection points and affine vertices of closed curves on 2-dimensional affine flat tori

This paper deals with a geometric problem on inflection points and affine vertices for closed curves in an affine flat torus. We show that the least number of inflection points lying on a closed curve that is not homotopic to zero is 2 if the torus is affinely equivalent to a euclidean torus and 0 otherwise. We consider also the number of affine vertices on a strictly convex closed curve on a flat torus. An explicit example of a closed curve with six affine vertices is given.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

与给定多边形相切的可调广义Ball闭曲线

讨论了与给定控制多边形相切的分段三次、五次和六次可调广义Ball曲线的构造方法,所构造的曲线分别是C1,C2和C3连续的,而且对切线多边形是保形的.曲线上的所有广义Ball曲线段的控制点由切线多边形的顶点直接计算产生.给出了在保持公共连接点处相应连续的情况下,内控制点的活动范围.曲线可以在一定范围内做局部修改.计算实例...     

一类带有给定切线多边形的样条曲线

利用带有形状参数的基函数,构造与给定切线多边形相切的样条曲线,所构造的曲线是C2和C3连续的,且对切线多边形是保形的.曲线上的所有控制点可由多边形顶点直接计算产生,曲线具有局部修改性.最后,以实例说明算法是有效的.     

CAN A CUBIC SPLINE CURVE BE G3

This paper proposes a method to construct an G³cubic spline curve from any given open control polygon.For any two inner Bezier points on each edge of a control polygon,we can de ne each Bezier junction point such that the spline curve is G2-continuous.Then by suitably choosing the inner Bezier points,we can construct a global G³spline curve.The curvature combs and curvature plots show the advantage of the G³cubic spline curve in contrast with the traditional C2 cubic spline curve.     

关于空间曲缐多边形的全曲率

<正> 在另一文内作者证明了这样定理:设一关闭挠曲缐 C 有一角点它的内角是θ,则它的全曲率∮_(c)kds≥π+θ.这结果可以看做关于关闭挠曲线全曲率的 Fenchel 定理的推广.从这结果很自然会引起一个问题,就是如果所论闭曲缐的角点多于一个,则     

Finding a Guard that Sees Most and a Shop that Sells Most

We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set in the plane. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time, and the rigid motion doing so in near-cubic time.     

Offset-polygon annulus placement problems

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.