An Algorithm for Partitioning Polygons into Convex Parts

An algorithm for partitioning arbitrary simple polygons into a number of convex parts was presented. The concave vertices were determined first, and then they were moved by using the method connecting the concave vertices with the vertices of falling into its region B,so that the primary polygon could be partitioned into two subpolygons. Finally, this method was applied recursively to the subpolygons until all the concave vertices were removed. This algorithm partitions the polygon into O(l) convex parts, its time complexity is max(O(n),O(l 2)) multiplications, where n is the number of vertices of the polygon and l is the number of the concave vertices.

An Optimal Algorithm for Solving Collision Distance Between Convex Polygons in Plane

In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.

A High Frequency Boundary Element Method for Scattering by Convex Polygons with Impedance Boundary Conditions

We consider scattering of a time harmonic incident plane wave by a convex polygon with piecewise constant impedance boundary conditions.Standard finite or boundary element methods require the number of degrees of freedom to grow at least linearly with respect to the frequency of the incident wave in order to maintain accuracy.Extending earlier work by Chandler-Wilde and Langdon for the sound soft problem,we propose a novel Galerkin boundary element method,with the approximation space consisting of the products of plane waves with piecewise polynomials supported on a graded mesh with smaller elements closer to the corners of the polygon.Theoretical analysis and numerical results suggest that the number of degrees of freedom required to achieve a prescribed level of accuracy grows only logarithmically with respect to the frequency of the incident wave.

The Minimum Number of Points Taking Part in k-Sets in Sets of Unaligned Points

The study of k- sets is a very relevant topic in the research area of computational geometry. The study of the maximum and minimum number of k-sets in sets of points of the plane in general position, specifically, has been developed at great length in the literature. With respect to the maximum number of k-sets, lower bounds for this maximum have been provided by Erdaos et al., Edelsbrunner and Welzl, and later by Toth. Dey also stated an upper bound for this maximum number of k-sets. With respect to the minimum number of k-set, this has been stated by Erdos el al. and, independently, by Lovasz et al. In this paper the authors give an example of a set ofn points in the plane in general position （no three collinear）, in which the minimum number of points that can take part in, at least, a k-set is attained for every k with 1 ≤ k 〈 n/2. The authors also extend Erdos＇s result about the minimum number of points in general position which can take part in a k-set to a set ofn points not necessarily in general position. That is why this work complements the classic works we have mentioned before.

Efficient Inverse Method for Structural Identification Considering Modeling and Response Uncertainties

The inverse problem analysis method provides an effective way for the structural parameter identification.However,uncertainties wildly exist in the practical engineering inverse problems.Due to the coupling of multi-source uncertainties in the measured responses and the modeling parameters,the traditional inverse method under the deterministic framework faces the challenges in solving mechanism and computing cost.In this paper,an uncertain inverse method based on convex model and dimension reduction decomposition is proposed to realize the interval identification of unknown structural parameters according to the uncertain measured responses and modeling parameters.Firstly,the polygonal convex set model is established to quantify the epistemic uncertainties of modeling parameters.Afterwards,a space collocation method based on dimension reduction decomposition is proposed to transform the inverse problem considering multi-source uncertainties into a few interval inverse problems considering response uncertainty.The transformed interval inverse problem involves the two-layer solving process including interval propagation and optimization updating.In order to solve the interval inverse problems considering response uncertainty,an efficient interval inverse method based on the high dimensional model representation and affine algorithm is further developed.Through the coupling of the above two strategies,the proposed uncertain inverse method avoids the time-consuming multi-layer nested calculation procedure,and then effectively realizes the uncertainty identification of unknown structural parameters.Finally,two engineering examples are provided to verify the effectiveness of the proposed uncertain inverse method.

Another Simple and Elementary Proof of the Classical Isoperimetric Inequality

In this short note we will give another simple and elementary proof of the classical isoperimetric inequality in the Euclidean plane.

A Quadratic Serendipity Finite Volume Element Method on Arbitrary Convex Polygonal Meshes

Based on the idea of serendipity element,we construct and analyze the first quadratic serendipity finite volume element method for arbitrary convex polygonalmeshes in this article.The explicit construction of quadratic serendipity element shape function is introduced from the linear generalized barycentric coordinates,and the quadratic serendipity element function space based on Wachspress coordinate is selected as the trial function space.Moreover,we construct a family of unified dual partitions for arbitrary convex polygonal meshes,which is crucial to finite volume element scheme,and propose a quadratic serendipity polygonal finite volume element method with fewer degrees of freedom.Finally,under certain geometric assumption conditions,the optimal H1 error estimate for the quadratic serendipity polygonal finite volume element scheme is obtained,and verified by numerical experiments.

A Fast Hidden-line Removal Algorithm for 3-Dimensional Buildings

in this paper, a fast hidden-line removal method for 3D buildings , which is based on thesubtraction of a convex polygon from another one in linear time, is presented. Also, the facetscontaining holes are quickly divided into a lot of convex polygons, say, triangles and convexquadrilaterals. The algorithm for the polygon division runs in O( (k+1) (n-3)) , where n is thetotal number of the vertices of the merged loop of the facet, and k is the number of the concavevertices of the merged one.

A novel method of determining the optimal polyhedral orientation for discrete global grid systems applicable to regionalscale areas of interest

The polyhedral discrete global grid system(DGGS)is a multi-resolution discrete earth reference model supporting the fusion and processing of multi-source geospatial information.The orientation of the polyhedron relative to the earth is one of its key design choices,used when constructing the grid system,as the efficiency of indexing will decrease if local areas of interest extend over multiple faces of the spherical polyhedron.To date,most research has focused on global-scale applications while almost no rigorous mathematical models have been established for determining orientation parameters.In this paper,we propose a method for determining the optimal polyhedral orientation of DGGSs for areas of interest on a regional scale.The proposed method avoids splitting local or regional target areas across multiple polyhedral faces.At the same time,it effectively handles geospatial data at a global scale because of the inherent characteristics of DGGSs.Results show that the orientation determined by this method successfully guarantees that target areas are located at the center of a single polyhedral face.The orientation process determined by this novel method reduces distortions and is more adaptable to different geographical areas,scales,and base polyhedrons than those employed by existing procedures.

GLOBAL UNIQUENESS IN THE INVERSE ACOUSTIC SCATTERING PROBLEM WITHIN POLYGONAL OBSTACLES

The authors prove the uniqueness in the inverse acoustic scattering problem within convex polygonal domains by a single incident direction in the sound-soft case and the sound-hard case, and by two incident directions in the case of the impedance boundary condition. The proof is based on analytic continuation on a straight line.

Statistical and Geometrical Way of Model Selection for a Family of Subdivision Schemes

The objective of this article is to introduce a generalized algorithm to produce the m-point n-ary approximating subdivision schemes(for any integer m, n ≥ 2). The proposed algorithm has been derived from uniform B-spline blending functions. In particular, we study statistical and geometrical/traditional methods for the model selection and assessment for selecting a subdivision curve from the proposed family of schemes to model noisy and noisy free data. Moreover, we also discuss the deviation of subdivision curves generated by proposed family of schemes from convex polygonal curve. Furthermore, visual performances of the schemes have been presented to compare numerically the Gibbs oscillations with the existing family of schemes.