Secure Two-Party Computational Geometry

Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric. problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.

3D Modelling of Biological Systems for Biomimetics

With the advanced development of computer-based enabling technologies, many engineering, medical, biology, chemistry, physics and food science etc have developed to the unprecedented levels, which lead to many research and development interests in various multi-discipline areas. Among them, biomimetics is one of the most promising and attractive branches of study. Biomimetics is a branch of study that uses biological systems as a model to develop synthetic systems. To learn from nature, one of the fundamental issues is to understand the natural systems such animals, insects, plants and human beings etc. The geometrical characterization and representation of natural systems is an important fundamental work for biomimetics research. 3D modeling plays a key role in the geometrical characterization and representation, especially in computer graphical visualization. This paper firstly presents the typical procedure of 3D modelling methods and then reviews the previous work of 3D geometrical modelling techniques and systems developed for industrial, medical and animation applications. Especially the paper discusses the problems associated with the existing techniques and systems when they are applied to 3D modelling of biological systems. Based upon the discussions, the paper proposes some areas of research interests in 3D modelling of biological systems and for Biomimetics.

Characteristic Polynomial Assignment in 2-D System

The closed loop polynomial assignment problems of 2D systems Roesser model with multiple inputs were studied. The problems were transferred to a rational map and were assigned a sate feedback and output feedback. Sufficient conditions for the system were derived using the algebraic geometric methods.

Some Properties of the Sum and Geometric Differences of Minkowski

The sets of Minkowski algebraic sum and geometric difference are considered. The purpose of the research in this paper is to apply the properties of Minkowski sum and geometric difference to fractional differential games. This paper investigates the geometric properties of the Minkowski algebraic sum and the geometric difference of sets. Various examples are considered that calculate the geometric differences of sets. The results of the research are presented and proved as a theorem. At the end of the article, the results were applied to fractional differential games.

3D Surface Editing Based on Level-Sets

A novel method which integrates the topological flexibility of the level-set approach and the simplicity of point-sampled surfaces is proposed. The grid structure resulted from the level-set approach not only offers a wide range of powerful surface editing techniques for the point set surface editing, but also facilitates the topological change with ease. With the aid of point-based resampling, the method updates the surface shape of the point-based geometry quickly without worrying about point connectivity at all. The point set surface can also change its topology properly whenever a collision with other parts of itself is detected. The experiment demonstrates their effectiveness on several scanned objects and scan-converted models. Four examples of surface editing operations： smoothing, tapering, deforming, and Boolean operations, are presented.

Slicing Strategy for Selective Laser Melting

Selective laser melting （SLM） is one of the most popular additive manufacturing （AM） technologies for metal parts. Slicing result, especially for the different dimensional slicing geometry and its topology, plays an important role because of the thermodynamic behavior of metal powders. To get correct geometry and reliable topology, a slicing strategy for SLM is proposed. The unavoidable numerical error caused by sampling and geometric transformation is suppressed firstly, according to shifting the z-coordinate of a vertex with a small value such the shifted vertex is on a slicing plane. The result of vertex-shifting makes it possible to identify different geometric features such as skin surfaces, overhang surfaces, extreme edges and volumetric solid. Second, from geometric primitives a hierarchy of axis-aligned bounding boxes （AABBs） is constructed and used to speed up intersection of slicing planes against sets of triangles. All intersecting segments are given different signs to depict their geometric or topological information. Based the different signs, the different dimensional geometry that is eventually represented by simple and anticlockwise oriented polygons, are identified. Finally, the polygons are classified and nested in a multi-tree data structure set to produce correct topological relations. The result of digital and physical experiments shows the proposed slicing strategy is feasible and robust.

Multi-scale visual analysis of cycle characteristics in spatially-embedded graphs

We present a visual analysis environment based on a multi-scale partitioning of a 2d domain intoregions bounded by cycles in weighted planar embedded graphs.The work has been inspired by anapplication in granular materials research,where the question of scale plays a fundamental role inthe analysis of material properties.We propose an efficient algorithm to extract the hierarchical cyclestructure using persistent homology.The core of the algorithm is a filtration on a dual graph exploitingAlexander’s duality.The resulting partitioning is the basis for the derivation of statistical properties thatcan be explored in a visual environment.We demonstrate the proposed pipeline on a few syntheticand one real-world dataset.

Secure Two-Party Point-Circle Inclusion Problem

Privacy-preserving computational geometry is a special secure multi-party computation and has many applications. Previous protocols for determining whether a point is inside a circle are not secure enough. We present a two-round protocol for computing the distance between two private points and develop a more efficient protocol for the point-circle inclusion problem based on the distance protocol. In comparison with previous solutions, our protocol not only is more secure but also reduces the number of communication rounds and the number of modular multiplications significantly.

Method to improve the performance of reflectance diffuse optical imaging based on polygonal optical fibers arrangement

In order to improve the performance of reflectance diffuse optical imaging （rDOI）, a novel polynomial geometry （PG） of optical fibers arrangement is proposed. Polynomial geometry is based on the hexagonal geometry （HG） and multicentered double-density （MD） mode. The overlapping sensitivity matrix, area ratio （AR）, reconstruction image, two-absorber model, and contrast-to-noise ratio （CNR） in different depths are used to evaluate the performance of PG. The other three geometries including HG, rectangular geometry （RG）, and MD mode are also compared with PG. The deformation of the reconstruction images is evaluted by circular ratio （CR）. The results prove that the proposed PG has high performance and minimum deformation in quality of reconstruction image in rDOI.

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.

A 3D hybrid grid generation technique and a multigrid/parallel algorithm based on anisotropic agglomeration approach

A hybrid grid generation technique and a multigrid/parallel algorithm are presented in this paper for turbulence flow simulations over three-dimensional （3D） complex geometries. The hybrid grid generation technique is based on an agglomeration method of anisotropic tetrahedrons. Firstly, the complex computational domain is covered by pure tetrahedral grids, in which anisotropic tetrahedrons are adopted to discrete the boundary layer and isotropic tetrahedrons in the outer field. Then, the anisotropic tetrahedrons in the boundary layer are agglomerated to generate prismatic grids. The agglomeration method can improve the grid quality in boundary layer and reduce the grid quantity to enhance the numerical accuracy and efficiency. In order to accelerate the convergence history, a multigrid/parallel algorithm is developed also based on anisotropic agglomeration approach. The numerical results demonstrate the excellent accelerating capability of this multigrid method.

Searching a Polygonal Region by Two Guards

We study the problem of searching for a mobile intruder in a polygonal region P by two guards. The objective is to decide whether there should exist a search schedule for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of P continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal O（n） time algorithm to determine the two-guard searchability in a polygon, and an O（n log n ＋ m） time algorithm to generate a search schedule, if it exists, where n is the number of vertices of P and m （≤ n^2） is the number of search instructions reported.

Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually ＂see＂ an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover, an optimal O（n） time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O（n log n ＋ I） time algorithm for generating a search schedule if it exists, where I （〈 3n^2） is the number of search instructions reported. Our results improve upon the previously known O（n^2） time and space bounds.

A quantum search algorithm of two-dimensional convex hull

Despite the rapid development of quantum research in recent years,there is very little research in computational geometry.In this paper,to achieve the convex hull of a point set in a quantum system,a quantum convex hull algorithm based on the quantum maximum or minimum searching algorithm(QUSSMA)is proposed.Firstly,the novel enhanced quantum representation of digital images is employed to represent a group of point set,and then the QUSSMA algorithm and vector operation are used to search the convex hull of the point set.In addition,the algorithm is simulated and compared with the classical algorithm.It is concluded that the quantum algorithm accelerates the classical algorithm when the Mpvalue of the convex hull point is under a certain condition.

Contact theory and algorithm

In discontinuous computations,contacts between two general blocks A and B are common and represent a fundamental problem.This paper presents a mathematically proven theory and algorithm to address this problem.In the proposed approach,a reference point a0 is selected from block A,and the contacts between blocks A and B are transferred to the contact of the reference point a0 and the entrance block E(A,B).Discontinuity related computations DEM,DDA,and FEM can use this mathematically proven theory and algorithm directly.

Cubic Spiral Transition Matching G^(2) Hermite End Conditions

This paper explores the possibilities of very simple analysis on derivation of spiral regions for a single segment of cubic function matching positional,tangential,and curvature end conditions.Spirals are curves of monotone curvature with constant sign and have the potential advantage that the minimum and maximum curvature exists at their end points.Therefore,spirals are free from singularities,inflection points,and local curvature extrema.These properties make the study of spiral segments an interesting problem both in practical and aesthetic applications,like highway or railway designing or the path planning of non-holonomic mobile robots.Our main contribution is to simplify the procedure of existence methods while keeping it stable and providing flexile constraints for easy applications of spiral segments.

Robust reconstruction of curved line structures in noisy point clouds

Point-based geometry representations have become widely used in numerous contexts,ranging from particle-based simulations,over stereo image matching,to depth sensing via light detection and ranging.Our application focus is on the reconstruction of curved line structures in noisy 3D point cloud data.Respective algorithms operating on such point clouds often rely on the notion of a local neighborhood.Regarding the latter,our approach employs multi-scale neighborhoods,for which weighted covariance measures of local points are determined.Curved line structures are reconstructed via vector field tracing,using a bidirectional piecewise streamline integration.We also introduce an automatic selection of optimal starting points via multi-scale geometric measures.The pipeline development and choice of parameters was driven by an extensive,automated initial analysis process on over a million prototype test cases.The behavior of our approach is controlled by several parameters—the majority being set automatically,leaving only three to be controlled by a user.In an extensive,automated final evaluation,we cover over one hundred thousand parameter sets,including 3D test geometries with varying curvature,sharp corners,intersections,data holes,and systematically applied varying types of noise.Further,we analyzed different choices for the point of reference in the co-variance computation;using a weighted mean performed best in most cases.In addition,we compared our method to current,publicly available line reconstruction frameworks.Up to thirty times faster execution times were achieved in some cases,at comparable error measures.Finally,we also demonstrate an exemplary application on four real-world 3D light detection and ranging datasets,extracting power line cables.

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.

Structurally coupled characteristics of rotor blade geometrically exact formulation

In rotor dynamics,blades are normally modelled as a slender beam,in which elastic deformations are coupled with each other.To identify these coupling effects,new rigid-flexible structural model for helicopter rotor system is proposed in this paper.Finite rotations of the whole blade(on flapwise,lagwise,and torsional)are described as three global rigid degrees of freedom.The nonlinear deformation geometrics of the beam is built on geometrically exact beam theory.New expressions for blade strain energy,kinetic energy,and virtual work of various kinds of external forces are derived as functions of finite rotations and elastic deformations.To quantify the coupling characteristics,following the definition of coupling factor in electromagnetics,a new coupling factor between two modal components on each mode is introduced in modal analysis.Simulations show that the new structural model is highly capable of solving static and dynamic problems in rotor system and the maximum deformation that moderate deformation beam theory can predict might be 15%of beam length.After the new coupling factor is applied to study structurally coupled characteristics of rotor blade,it can be concluded that closeness of natural frequencies likely indicates considerable coupling between corresponding DOFs in structure.

An Optimal Online Algorithm for Halfplane Intersection

The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.